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

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

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

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

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

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

כעת נקבל מצב אבסורד לגבי הריצה של $H^{\prime }$ על הקלט $x=⟨H^{\prime }⟩$, כלומר עבור ההרצה $H^{\prime }(⟨H^{\prime }⟩)$:

1. אם המכונה עוצרת בהרצה זו, אז בהכרח $H(⟨H^{\prime }⟩,⟨H^{\prime }⟩)$ החזירה תשובה שלילית (מפני שהיא השלב הראשון בריצת $H^{\prime }$ שכתוצאתו הוחלט לעצור). אבל לפי ההגדרה, משמעות תשובה שלילית זו היא ש־$H^{\prime }(⟨H^{\prime }⟩)$ איננה עוצרת, ולכן יש סתירה.
2. לעומת זאת, אם המכונה איננה עוצרת בהרצה זו, אז בהכרח $H(⟨H^{\prime }⟩,⟨H^{\prime }⟩)$ החזירה תשובה חיובית (שוב, מפני שהיא השלב הראשון בריצת $H^{\prime }$ שכתוצאתו הוחלט להיכנס ללולאה אינסופית). אבל לפי ההגדרה של H, משמעות תשובה חיובית זאת היא ש־$H^{\prime }$ עוצרת על הקלט $⟨H^{\prime }⟩$, וזו שוב סתירה.

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

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

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

ראשית נראה שיש יותר שפות ממחרוזות. תבנית:טענה

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

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

תבנית:תורת החישוביות