תורת החישוביות/כריעות שפות

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

בפרק זה נראה שלוש מחלקות של בעיות. באופן לא מדוייק, השפות הכריעות הן משפחת השפות שאפשר לזהות באופן מלא, ואילו שפות כריעות למחצה חיובית ושפות כריעות למחצה שלילית הן שפות שאפשר לזהות באופן חלקי.

בשאר חלקי הפרק נעסוק במחלקות אלו. הפרק קיום שפות שאינן כריעות מראה שאכן יש שפות שאי אפשר לזהותן (כפי שראינו מעט בחלק המוטיבציה במבוא). הפרקים רדוקציה חישובית ומשפט רייס מראים שתי טכניקות כלליות ביותר, שכ"א מהן יכולה לשמש להוכחה ששפה כלשהי נמצאת (או לא) באחת ממחלקות אלו. הפרק אי-הפרדתיות רקורסיבית דן במאפיין נוסף של שפות במחלקות אלו.

סוגי הכריעות ומחלקות הכריעות

כריעות (מלאה)

כפי שראינו, התנהגות מ״ט על קלט מסוים יכולה להיות אחת משלוש האפשרויות הבאות: קבלה, דחייה, או אי־עצירה. כשאנו כותבים למשל תוכנית מחשב הפותרת בעיה כלשהי, מן הסתם לא נרצה שהיא "תתקע" ותכנס ללולאה אינסופית. מבחינה פרקטית, יותר מעניינות אותנו תוכנות־מחשב שלא נתקעות, ותמיד מצליחות לסיים את החישוב. באופן דומה, עבור בעיות הכרעה, נרצה להגדיר תחילה את המכונות שמתנהגות "יפה", כלומר תמיד עוצרות (מקבלות או דוחות כל קלט), ולעולם לא "נתקעות" בלולאה אינסופית.

להלן דוגמאות לשפות כריעות:

1. השפה ${\mathrm{\Sigma }}^{*}$ – לכל קלט, בצעד החישוב הראשון המכונה עוברת ל־$q_{acc}$.
2. השפה הריקה $\mathrm{\varnothing }$ – לכל קלט, המכונה עוברת בצעד החישוב הראשון ל־$q_{rej}$.
3. כל שפה סופית $L=\{a_1,a_2,\dots ,a_n\}$ – נבדוק כל מילה אפשרית. מכיוון שכמות המילים סופית, נדרשים מספר סופי של מצבים (ובפרט, זו שפה רגולרית)
4. כל שפה רגולרית – אוטומט סופי הוא מקרה פרטי של מכונת טיורינג, לכן מ"ט מסוגלת לחשב כל מה שאוטומט סופי יכול.
5. $\}$ מספר האפסים בקלט שווה למספר האחדות $L=\{x\in \{0,1{\}}^{*}\mid$. (זו שפה לא-רגולרית)

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

כריעות למחצה חיובית

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

דוגמאות

להלן מספר דוגמאות לשפות נתנות למניה רקורסיבית:

1. השפה האוניברסלית מוגדרת כך: $L_U=\{(⟨M⟩,x)\mid x\in L(M)\}$תבנית:ש

כל מילה בשפה זו מורכבת משתי מחרוזות – הראשונה היא קידוד של מכונה $M$ והשניה הינה מחרוזת כלשהי $x$. המילה $(⟨M⟩,x)$ שייכת לשפה האוניברסלית אם המחרוזת $x$ מתקבלת ע״י המכונה $M$.

נוכיח כריעות למחצה חיובית: נבנה מכונה אשר על הקלט $(⟨M⟩,x)$ מסמלצת הרצה של המכונה $M$ על הקלט $x$, ומתנהגת כמותה (כלומר, אם $M$ עצרה במצב $q_{acc}$, נקבל ואם עצרה ב־$q_{rej}$ – נדחה. אם $M$ אינה עוצרת, כך גם המכונה שבנינו.

2. שפת האלכסון מוגדרת כך: $L_D=\{⟨M⟩\mid ⟨M⟩\in L(M)\}$תבנית:ש

דהיינו, קידודי כל המכונות המקבלות את הקידוד של עצמן.

הקידוד של המכונה M ששפתה $L(M)={\mathrm{\Sigma }}^{*}$ שייך ל־$L_D$, כי $M$ מקבלת כל קלט ובפרט את המחרוזת $⟨M⟩$.

נוכיח כריעות למחצה חיובית: כמקודם, נבנה מכונה שמסמלצת את הרצת $M$ על הקלט $⟨M⟩$, ומקבלת/דוחה בהתאם לסימולציית ההרצה.

3. שפת בעיית העצירה מוגדרת כך: $M\}$ עוצרת על $L_{HP}=\{(⟨M⟩,x)\mid x$תבנית:ש

נוכיח כריעות למחצה חיובית: נריץ את $M$ על $x$ – אם המכונה תעצור, נקבל. אחרת – $M$ לא עצרה וגם המכונה המסמלצת בלולאה אינסופית, ואינה מקבלת את הקלט הנ״ל.

כריעות למחצה שלילית

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

תכונות מחלקות הכריעות

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

הייחסים בין קבוצות השפות

תבנית:טענה

תבנית:טענה הוכחה: תהי $M_1$ מ"ט המכריעה את $L_1$, ותהי $M_2$ מ"ט המכריעה את $L_2$.תבנית:ש נבנה מכונה M שמריצה את $M_1$ ולאחר מכן את $M_2$ (למשל, על סרט שני אליו מועתק הקלט בהתחלה). החזר "כן" אם אחת המכונות קיבלה, ואחרת – החזר "לא". נשים לב ששתי המכונות עוצרות על כל קלט ולכן גם M תעצור על כל קלט.

תבנית:טענה ההוכחה לעיל אינה מספיק טובה, מכיוון שייתכן ש־$M_1$ אינה עוצרת, ולכן לעולם לא נגיע לשלב בו אנחנו מריצים את $M_2$. במילים אחרות, אסור לנו להריץ את שתי המכונות בטור, וצריך להריץ אותן בצורה מקבילה, כל אחת על סרט אחר. מסמלצים צעד מ־$M_1$ ולאחריו צעד של $M_2$ וחוזר חלילה. אם אחת המכונות קיבלה – עוצרים ומקבלים. אם שתיהן בלולאה אינסופית, גם המכונה שבנינו לא תעצור (אך זה מותר עבור קלט שאינו בשפה, לפי הגדרת המחלקה $RE$).

תבנית:טענה (תרגיל: הוכח).