תורת החישוביות/כריעות שפות/ארגז חול

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

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

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

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

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

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

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

דוגמה: להלן דוגמאות לשפות כריעות: השפה $\Sigma ^{*}$ – לכל קלט, בצעד החישוב הראשון המכונה עוברת ל־$q_{acc}$. השפה הריקה $\emptyset$ – לכל קלט, המכונה עוברת בצעד החישוב הראשון ל־$q_{rej}$. כל שפה סופית $L=\{a_{1},a_{2},\ldots ,a_{n}\}$ – נבדוק כל מילה אפשרית. מכיוון שכמות המילים סופית, נדרשים מספר סופי של מצבים (ובפרט, זו שפה רגולרית) כל שפה רגולרית – אוטומט סופי הוא מקרה פרטי של מכונת טיורינג, לכן מ"ט מסוגלת לחשב כל מה שאוטומט סופי יכול. $\}$ מספר האפסים בקלט שווה למספר האחדים $L=\{x\in \{0,1\}^{*}\mid$. (זו שפה לא-רגולרית)

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

הגדרה: מחלקת השפות הכריעות (או הרקורסיביות) נגדיר את המחלקה $R$ כקבוצת השפות הכריעות (לחלופין, ניתנות להכרעה או רקורסיביות, Recursive) $R=\{L\;|\;L{\text{ recursive}}\}$

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

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

הגדרה: נאמר שמ"ט $M$ מכריעה למחצה חיובית או מונה רקורסיבית שפה $L$ אם היא מקבלת כל מילה ב־$L$ ואיננה מקבלת מילה שאיננה ב-$L$ שפה $L$ ניתנת למנייה רקורסיבית אם קיימת מ"ט $M$ שמכריעה אותה למחצה חיובית. שפה $L$ אינה נתנת למניה רקורסיבית אם לא קיימת מ״ט המקבלת אותה למחצה חיובית.

מעט אטימולוגיה. שפה נקראת "נתנת למניה רקורסיבית" מהסיבה הבאה. נניח ש-$L$ היא שפה נתנת למניה רקורסיבית ע"י מ"ט $M$. נקח מניה כלשהי של המחרוזות על פני $\Sigma ^{*}$. כעת נפעיל את $M$ צעד אחד על המחרוזת הראשונה במניה, 2 צעדים על כ"א מ2 המחרוזות הראשונות במניה, 3 צעדים על כ"א מ3 -המחרוזות הראשונות במניה, וכו'. ברור שכל מחרוזת השייכת לL, תזוהה ככזו בשלב כלשהו ע"י כך שM תעצור ותקבל אותה. בכל פעם שמילה מתקבלת, נרשום אותה ברשימה בצד. מצאנו דרך לבצע מניה של כל המחרוזות של $L$.

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

דוגמה: השפה האוניברסלית השפה האוניברסלית מוגדרת כך: $L_{U}=\{(\langle M\rangle ,x)\mid x\in L(M)\}$ כל מילה בשפה זו מורכבת משתי מחרוזות – הראשונה היא קידוד של מכונה $M$ והשניה הינה מחרוזת כלשהי $x$. המילה $(\langle M\rangle ,x)$ שייכת לשפה האוניברסלית אם המחרוזת $x$ מתקבלת ע״י המכונה $M$. נוכיח כריעות למחצה חיובית: נבנה מכונה אשר על הקלט $(\langle M\rangle ,x)$ מסמלצת הרצה של המכונה $M$ על הקלט $x$, ומתנהגת כמותה (כלומר, אם $M$ עצרה במצב $q_{acc}$, נקבל ואם עצרה ב־$q_{rej}$ – נדחה. אם $M$ אינה עוצרת, כך גם המכונה שבנינו.

דוגמה: שפת האלכסון שפת האלכסון מוגדרת כך: $L_{D}=\{\langle M\rangle \mid \langle M\rangle \in L(M)$ דהיינו, קידודי כל המכונות המקבלות את הקידוד של עצמן. הקידוד של המכונה M ששפתה $L(M)=\Sigma ^{*}$ שייך ל־$L_{D}$, כי $M$ מקבלת כל קלט ובפרט את המחרוזת $\langle M\rangle$. נוכיח כריעות למחצה חיובית: כמקודם, נבנה מכונה שמסמלצת את הרצת $M$ על הקלט $\langle M\rangle$, ומקבלת/דוחה בהתאם לסימולציית ההרצה.

דוגמה: שפת בעיית העצירה שפת בעיית העצירה מוגדרת כך: $M\}$ עוצרת על $L_{HP}=\{(\langle M\rangle ,x)\mid x$ נוכיח כריעות למחצה חיובית: נריץ את $M$ על $x$ – אם המכונה תעצור, נקבל. אחרת – $M$ לא עצרה וגם המכונה המסמלצת בלולאה אינסופית, ואינה מקבלת את הקלט הנ״ל.

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

הגדרה: מחלקת השפות הכריעות למחצה חיובית (או הנתנות למניה רקורסיביות) נגדיר את המחלקה $RE$ כקבוצת השפות הכריעות למחצה חיובית (לחלופין, נתנות למניה רקורסיבית, Recursively Enumerable) $RE=\{L\;|\;L{\text{ recursively enumerable}}\}$

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

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

הגדרה: נאמר שמ"ט $M$ מכריעה למחצה שלילית היא דוחה כל מילה שאיננה ב־$L$ ואיננה דוחה מילה ב-$L$

הגדרה: מחלקת השפות הכריעות למחצה שלילית) נגדיר את המחלקה $coRE$ כקבוצת השפות הכריעות למחצה שלילית (coRecursively Enumerable) $RE=\{L\;|\;L{\text{ co-recusively enumerable}}\}$

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

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

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

טענה: $R\subseteq RE$   ,   $R\subseteq coRE$ $R=RE\cap coRE$

הוכחה: {{{1}}}

טענה: 3.  $\ R$ סגורה למשלים: אם $L\in R$ אז גם השפה המשלימה, ${\overline {L}}\in R$

הוכחה: {{{1}}}

טענה: 4.  $R$ סגורה לאיחוד: לכל $L_{1},L_{2}\in R$ מתקיים $L_{1}\cup L_{2}\in R$

הוכחה: תהי $M_{1}$ מ"ט המכריעה את $L_{1}$, ותהי $M_{2}$ מ"ט המכריעה את $L_{2}$.
נבנה מכונה M שמריצה את $M_{1}$ ולאחר מכן את $M_{2}$ (למשל, על סרט שני אליו מועתק הקלט בהתחלה). החזר "כן" אם אחת המכונות קיבלה, ואחרת – החזר "לא". נשים לב ששתי המכונות עוצרות על כל קלט ולכן גם M תעצור על כל קלט.

טענה: 5.  $RE$ סגורה לאיחוד: לכל $L_{1},L_{2}\in RE$ מתקיים $L_{1}\cup L_{2}\in RE$

ההוכחה לעיל אינה מספיק טוב, מכיוון שייתכן ש־$M_{1}$ אינה עוצרת, ולכן לעולם לא נגיע לשלב בו אנחנו מריצים את $M_{2}$. במילים אחרות, אסור לנו להריץ את שתי המכונות בטור, וצריך להריץ אותן בצורה מקבילה, כל אחת על סרט אחר. מסמלצים צעד מ־$M_{1}$ ולאחריו צעד של $M_{2}$ וחוזר חלילה. אם אחת המכונות קיבלה – עוצרים ומקבלים. אם שתיהן בלולאה אינסופית, גם המכונה שבנינו לא תעצור (אך זה מותר עבור קלט שאינו בשפה, לפי הגדרת המחלקה $\ RE$).

טענה: 5.  $coRE$ סגורה לאיחוד   6.  $R,RE,coRE$ סגורות לחיתוך ושרשור

(תרגיל: הוכח).

-

ארגז חול

-