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

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

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

קיום שפות לא כריעות

בכריעות למחצה חיובית, ראינו את שפת בעיית העצירה, $L_{\text{HP}}$. נראה ששפה זו איננה כריעה (זו למעשה פורמליזציה של מה שראינו בחלק המוטיווציה במבוא לספר).

טענה:           השפה $L_{\text{HP}}$ אינה כריעה,     $L_{\text{HP}}\notin R$

הוכחה: נניח, על דרך השלילה, שקיימת מ"ט המכריעה את $L_{\text{HP}}$, כלומר, לכל קלט $(\langle M\rangle ,x)$ המכונה עוצרת ומקבלת/דוחה בהתאם לשאלה 'האם המכונה $M$ עוצרת על קלט $x$'. נקרא למכונה זו $H$. כעת נבנה את המכונה $H'$ באופן הבא:

1. בהנתן הקלט קידוד מ"ט $M$, המכונה קודם תריץ את $H(\langle M\rangle ,\langle M\rangle )$, (נזכור שתמיד חלק זה עוצר, שכן הנחתנו בשלילה היא שהבעיה כריעה, ו־$H$ מימוש שלה).
2. אם התשובה חיובית, אז $H'$ תכנס ללולאה אינסופית. אחרת, היא תעצור.

כעת נקבל מצב אבסורד לגבי הריצה של $H'$ על הקלט $x=\langle H'\rangle$, כלומר עבור ההרצה $H'(\langle H'\rangle )$:

1. אם המכונה עוצרת בהרצה זו, אז בהכרח $H(\langle H'\rangle ,\langle H'\rangle )$ החזירה תשובה שלילית (מפני שהיא השלב הראשון בריצת $H'$ שכתוצאתו הוחלט לעצור). אבל לפי ההגדרה, משמעות תשובה שלילית זו היא ש־$H'(\langle H'\rangle )$ איננה עוצרת, ולכן יש סתירה.
2. לעומת זאת, אם המכונה איננה עוצרת בהרצה זו, אז בהכרח $H(\langle H'\rangle ,\langle H'\rangle )$ החזירה תשובה חיובית (שוב, מפני שהיא השלב הראשון בריצת $H'$ שכתוצאתו הוחלט להיכנס ללולאה אינסופית). אבל לפי ההגדרה של H, משמעות תשובה חיובית זאת היא ש־$H'$ עוצרת על הקלט $\langle H'\rangle$, וזו שוב סתירה.

נסכם: השפה $L_{\text{HP}}$ אינה כריעה, אבל הינה כריעה למחצה חיובית (ע״י מ״ט טריוויאלית שעל $(\langle M\rangle ,x)$ שמנסה להריץ את M על הקלט x, ולראות האם M עוצרת..) לפיכך, $L_{\text{HP}}\in RE\smallsetminus R$.

קיום שפות לא כריעות למחצה

משיקולי מניה אפשר לראות שבהכרח יש אינספור שפות שלא רק שאינן כריעות, אלא שאינן אפילו כריעות למחצה (כלומר, יש אינספור שפות שאינן ב $RE\cup coRE$.)

ראשית נראה שיש יותר שפות ממחרוזות.

טענה: יש יותר שפות ממחרוזות (או: קבוצת כלל המחרוזות מעל $\Sigma$ היא בת-מניה, ואילו קבוצת כל השפות אינה בת-מניה).

הוכחה: קבוצת השפות הנה למעשה קבוצת כל תתי הקבוצות של $\Sigma ^{*}$. עוצמת קבוצה זו היא $2^{\aleph _{0}}=\aleph$.

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

נסמן את קבוצת כל המילים מעל $\Sigma$ ב־$x$ ונכתוב אותן לפי הסדר הלקסיקוגרפי:

$x=\{x_{0},x_{1},x_{2},\ldots \}$

נניח בשלילה שקבוצת כל השפות היא בת מנייה, ונסמנה ב־$A$.

$A=\{A_{0},A_{1},A_{2},\ldots \}$

נגדיר את השפה $D$:

$D=\{x_{i}\mid x_{i}\notin A_{i}\}$

כלומר, אם המילה $x_{0}$ נמצאת ב־$A_{0}$ אז היא לא ב־D. אך אם אינה ב־$A_{0}$ אז היא כן תהיה ב־$D$. ניתן לרשום זאת בצורת טבלה בה כל שורה היא אחת השפות $A_{i}$ וכל עמודה היא אחת המילים $x_{1}$ נסמן 1 אם $x_{i}\in A_{i}$ ו־0 אחרת.

${\begin{array}{c|cccc}&x_{0}&x_{1}&x_{2}&\ldots \\\hline A_{0}&\color {red}{1}&0&1&\\A_{1}&0&\color {red}{0}&1&\\A_{2}&1&0&\color {red}{1}&\\\vdots &&&&\ddots \end{array}}$

כעת נוכיח שהשפה $D$ אינה אחת מהשפות $A_{i}$. נביט על האלכסון. אם עבור מילה מסויימת $x_{i}\in D$ הרי שהיא אינה ב־$A_{i}$, ולכן $D\neq A_{i}$. למעשה – האלכסון מגדיר את ${\overline {D}}$.

קל לראות משיקולי ספירה שמספר השפות ב־$RE\cup coRE$ הוא לכל היותר מספר מ״ט השונות (כי כל מ״ט מגדירה שפה, ואם השפה ב־$RE\cup coRE$ אז קיימת מ״ט שמקבלת כל מילה בה או שקיימת מ״ט שדוחה כל מילה שאינה בה, לפי הגדרת המחלקות RE ו־coRE). בנוסף, כמות מ״ט הקיימות הוא לכל היותר כמות המחרוזות מעל האלפבית הבינארי, מכיוון שכל מ״ט ניתנת לקידוד למחרוזת בינארית. (העוצמה של $RE\cup coRE$ היא $\aleph _{0}$)

מאידך, עוצמת קבוצת כלל השפות היא גדולה בהרבה, $2^{\aleph _{0}}$. בפרט, יש הרבה יותר שפות מאשר גודל הקבוצה $RE\cup coRE$, משמע, קיימות שפות שאינן ב־$RE\cup coRE$ (למעשה, מרבית השפות אינן ב־$RE\cup coRE$).

הפרק הקודם: כריעות שפות

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

הפרק הבא: רדוקציה חישובית