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

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

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

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

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

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

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

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

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

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

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

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

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

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

הגדרה: נאמר שמ"ט $M$ מכריעה למחצה חיובית שפה $L$ אם היא מקבלת כל מילה ב־$L$ ואיננה מקבלת מילה שאיננה ב-$L$ שפה $L$ ניתנת להכרעה למחצה חיובית (נקרא גם ניתנת למנייה רקורסיבית) אם קיימת מ"ט $M$ שמכריעה אותה למחצה חיובית. שפה $L$ אינה ניתנת למניה רקורסיבית אם לא קיימת מ״ט המקבלת אותה למחצה חיובית. אוסף כלל השפות הניתנות להכרעה למחצה חיובית יסומן $RE$ (לחלופין, אוסף כלל השפות הניתנות למניה רקורסיבית, Recursively Enumerable): $\ \}$ קיימת מ"ט M שמקבלת את כל המילים ב־L ואינה מקבלת אף מילה שאינה ב־L (אבל לאו דווקא דוחה) $RE=\{L\mid$

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

דוגמאות

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

1. השפה האוניברסלית מוגדרת כך: $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$ אינה עוצרת, כך גם המכונה שבנינו.

2. שפת האלכסון מוגדרת כך: $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$, ומקבלת/דוחה בהתאם לסימולציית ההרצה.

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

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

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

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

הגדרה: נאמר שמ"ט $M$ מכריעה למחצה שלילית היא דוחה כל מילה שאיננה ב־$L$ ואיננה דוחה מילה ב-$L$. נסמן את קבוצת כלל השפות הכריעות למצה שלילית ב־$coRE$ (coRecursively Enumerable): $\}\;\;\;\$ קיימת מ"ט M שדוחה את כל המילים שאינן ב־L ואינה דוחה אף מילה ב־L (אבל לאו דווקא מקבלת) $\ \;\;\;coRE=\{L\mid$

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

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

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

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

הוכחה: קל לראות כי $R\subseteq RE\cap coRE$ כי אם השפה ניתנת להכרעה, אז ברור שקיימת מכונה שרק דוחה או רק מקבלת.

הכיוון השני: תהי $L\in RE\cap coRE$.
מכיוון ש־$L\in RE$ קיימת מ"ט $M_{1}$ שמקבלת כל מילה $x\in L$ ולא מקבלת $x\in {\overline {L}}$. באופן דומה, מכיוון ש־$L\in coRE$ קיימת מ"ט $M_{2}$ שדוחה כל מילה $x\in {\overline {L}}$ ולא דוחה אף $x\in L$.
נריץ את שתי המכונות במקביל (למשל ע״י שני סרטים): אם $M_{1}$ מקבלת, נקבל; ואם $M_{2}$ דוחה, נדחה (הראשון מביניהם). כל מילה $x$ או שייכת או לא שייכת ל־$L$ ולכן בהכרח אחד משני המקרים לעיל ייתרחש לאחר זמן סופי (כלומר, אם הקלט בשפה הוא בהכרח ייתקבל ע״י $M_{1}$ לאחר זמן סופי, ואם הוא לא בשפה הוא יידחה ע״י $M_{2}$ לאחר זמן סופי). לפיכך, המכונה שבנינו עוצרת על כל קלט אפשרי עם התשובה הנכונה.

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

הוכחה: אם $L\in R$ אז קיימת מ"ט M המכריעה את L. נבנה מ"ט ${\overline {M}}$ ע״י החלפת המצבים הסופיים: $q_{acc,M}=q_{rej,{\overline {M}}}$ ו־$q_{rej,M}=q_{acc,{\overline {M}}}$.
${\overline {M}}$ עוצרת על כל קלט (כי $M$ עוצרת על כל קלט), ובנוסף, ${\overline {M}}$ עונה הפוך מ־$M$, כלומר $L({\overline {M}})={\overline {L}}$ כנדרש.

טענה: 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$ סגורות לחיתוך ושרשור

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

הפרק הקודם: מודל לבעיות הכרעה

כריעות שפות תרגילים

הפרק הבא: קיום שפות שאינן כריעות