תורת החישוביות/כריעות שפות/ארגז חול
בחלק המוטיבציה במבוא לספר, ראינו שאי אפשר לכתוב תוכנית מחשב המזהה באופן כללי תוכנית מחשב כלשהי עוצרת כאשר היא מקבלת קלט כלשהו. בחלק זה נגדיר מושג זה ומושגים נלווים בצורה מדוייקת יותר, ונעסוק בתכונותיהם.
בפרק זה נראה שלוש מחלקות של בעיות. באופן לא מדוייק, השפות הכריעות הן משפחת השפות שאפשר לזהות באופן מלא, ואילו שפות כריעות למחצה חיובית ושפות כריעות למחצה שלילית הן שפות שאפשר לזהות באופן חלקי.
בשאר חלקי הפרק נעסוק במחלקות אלו. הפרק קיום שפות שאינן כריעות מראה שאכן יש שפות שאי אפשר לזהותן (כפי שראינו מעט בחלק המוטיבציה במבוא). הפרקים רדוקציה ומשפט רייס מראים שתי טכניקות כלליות ביותר, שכ"א מהן יכולה לשמש להוכחה ששפה כלשהי נמצאת (או לא) באחת ממחלקות אלו. הפרק אי-הפרדתיות רקורסיבית דן במאפיין נוסף של שפות במחלקות אלו.
סוגי הכריעות ומחלקות הכריעות
כריעות (מלאה)
אינטואיטיבית, שפה היא כריעה אם יש מכונת טיורינג העוצרת בוודאות על כל קלט, ומקבלת או דוחה בצורה נכונה האם הקלט שייך לשפה.
נוכל כמובן להגדיר את מחלקת השפות הכריעות.
תבנית:מבנה תבנית
כריעות למחצה חיובית
גם אם שפה איננה כריעה לחלוטין, עדיין אפשר לחשוב על כריעות חלקית במובן כלשהו. אינטואיטיבית, שפה היא כריעה למחצה חיובית אם יש מכונת טיורינג העוצרת בוודאות על כל קלט השייך לשפה ומקבלת אותה, ואיננה עוצרת ומקבלת קלט שאינו שייך לשפה (יחד עם זאת, אם הקלט אינו שייך לשפה, היא איננה חייבת לעצור).
להלן מספר דוגמאות לשפות נתנות למניה רקורסיבית:
גם כאן נוכל כמובן להגדיר את מחלקת השפות הנתנות למנייה רקורסיבית.
תבנית:מבנה תבנית
כריעות למחצה שלילית
הגדרה זו מזכירה לכריעות למחצה חיובית אך הפוכה לה. אינטואיטיבית, שפה היא כריעה למחצה שלילית אם יש מכונת טיורינג העוצרת בוודאות על כל קלט שאינו שייך לשפה ודוחה אותה, ואיננה עוצרת ודוחה קלט ששייך לשפה (יחד עם זאת, אם הקלט שייך לשפה, היא איננה חייבת לעצור).
תכונות מחלקות הכריעות
בחלק זה נוכיח תכונות של מחלקות הכריעות, ובפרט נוכיח שהתרשים הבא מתאר אותן.
תבנית:טענה הוכחה: תהי מ"ט המכריעה את , ותהי מ"ט המכריעה את .תבנית:ש נבנה מכונה M שמריצה את ולאחר מכן את (למשל, על סרט שני אליו מועתק הקלט בהתחלה). החזר "כן" אם אחת המכונות קיבלה, ואחרת – החזר "לא". נשים לב ששתי המכונות עוצרות על כל קלט ולכן גם M תעצור על כל קלט.
תבנית:טענה ההוכחה לעיל אינה מספיק טוב, מכיוון שייתכן ש־ אינה עוצרת, ולכן לעולם לא נגיע לשלב בו אנחנו מריצים את . במילים אחרות, אסור לנו להריץ את שתי המכונות בטור, וצריך להריץ אותן בצורה מקבילה, כל אחת על סרט אחר. מסמלצים צעד מ־ ולאחריו צעד של וחוזר חלילה. אם אחת המכונות קיבלה – עוצרים ומקבלים. אם שתיהן בלולאה אינסופית, גם המכונה שבנינו לא תעצור (אך זה מותר עבור קלט שאינו בשפה, לפי הגדרת המחלקה ).
תבנית:טענה (תרגיל: הוכח).