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

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

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

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

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

נניח, על דרך השלילה, שקיימת מ"ט כריעה, העונה על השאלה האם מ"ט $M$ עוצרת על קלט $x$. נקרא למכונה זו $H$. כעת נבנה את המכונה $H'$ באופן הבא:

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

כעת נקבל מצב אבסורד לגבי הריצה $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'(\langle H'\rangle )$ עוצרת, ולכן שוב יש סתירה.

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

משיקולי מניה אפשר לראות שבהכרח יש אינספור שפות שלא רק שאינן כריעות, אלא שאינן אפילו כריעות למחצה (כלומר, יש אינספור שפות ב-$\Sigma ^{*}\setminus RE$.)

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

טענה: יש יותר שפות ממחרוזות (או: קבוצת כלל המחרוזות מעל $\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}}$.

בעזרת הטענה הקודמת, אפשר לראות שבהכרח ישנן שפות ב$\Sigma ^{*}\setminus RE$

הוכחה: ההוכחה היא משיקולי ספירה.

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

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

-

ארגז חול

-