כריעות

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

במדעי המחשב, שפה נקראת כריעה אם קיים אלגוריתם שמקבל כקלט מילה, וקובע אם היא שייכת לשפה או לא. באופן פורמלי, שפה \ L תיקרא כריעה אם קיימת מכונת טיורינג M אשר עוצרת על כל קלט ומקבלת בדיוק את השפה \ L. במילים אחרות, אם מכונת טיורינג M תקבל כקלט מילה בשפה, היא תעצור במצב מקבל, ואם הקלט הוא מילה שאינה בשפה L, המכונה תעצור במצב דחייה. את מחלקת הבעיות (השפות) הכריעות מסמנים ב-R.

הדיון התאורטי בכריעות של שפות מקביל למושג החישוביות של אלגוריתמים. לדוגמה, השאלה אם קיים אלגוריתם אשר לכל מספר נתון יודע להגיד אם המספר ראשוני או פריק, שקול לשאלה אם השפה המכילה את כל המספרים הראשוניים, היא כריעה.

שפות שאינן כריעות[עריכת קוד מקור | עריכה]

קל להוכיח כי קיימות בעיות שלא ניתן לכתוב אלגוריתם לפתרונן, וכך למעשה, השפות המתאימות אינן כריעות. עובדה זו נובעת משיקולי ספירה: אנחנו יכולים ליצור רק \!\, \aleph_0 מכונות טיורינג ואילו יש \!\, \aleph שפות. את שאלת קיומן של שפות "מעניינות" (ז"א, ניתנות לתיאור סופי) שאינן כריעות, פתר אלן טיורינג כאשר הוכיח כי בעיית העצירה אינה כריעה. משפט רייס הרחיק לכת והוכיח כי למעשה כל בעיה ששואלת שאלה על אודות השפה של מכונת טיורינג והיא אינה שאלה טריוויאלית (כלומר, שהתשובה היא בהכרח כן או לא, ללא תלות בקלט), היא למעשה לא כריעה.


שפות כריעות-למחצה[עריכת קוד מקור | עריכה]

קיימות שפות שהן כריעות-למחצה (חיוביות), כלומר, לא קיימת מכונה אשר עוצרת עבור כל מילת קלט ומכריעה אם המילה בשפה או לא, אך קיימת מכונה אשר עוצרת כאשר הקלט שייך לשפה (וייתכן שאינה עוצרת כאשר הקלט אינו בשפה). הקבוצה המכילה את כלל השפות הללו מסומנת בתור המחלקה RE. בצורה מקבילה מגדירים את מחלקת השפות co-RE להיות קבוצת כל השפות L עבורן קיימת מכונת טיורינג אשר עוצרת ודוחה עבור כל מילת קלט שאינה בשפה L, אבל ייתכן שאינה עוצרת עבור מילים השייכות לשפה L.

החיתוך של שתי המחלקות לעיל מהווה את המחלקה R. מאידך, ישנן גם בעיות שהן ב-RE אך לא ב-co-RE ולהיפך, למשל, בעיית העצירה.

לעומת זאת, ישנן שפות שהן לא ב-RE וגם לא ב-co-RE. כך למשל בעיית העצירה המוכללת, ששואלת בהינתן כקלט מכונת טיורינג, אם המכונה עוצרת על כל הקלטים האפשריים. כמו כן, השפה המכילה את כל מכונות טיורינג שהשפות שלהן רגולריות, והשפה המכילה את כל מכונות טיורינג שהשפות שלהן חסרות הקשר, שתיהן לא ב- RE ולא ב- co-RE (ובפרט אינן כריעות).