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

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

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

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

עריכה

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

טענה:

          השפה   אינה כריעה,                

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

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

כעת נקבל מצב אבסורד לגבי הריצה של   על הקלט  , כלומר עבור ההרצה  :

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

נסכם: השפה   אינה כריעה, אבל הינה כריעה למחצה חיובית (ע״י מ״ט טריוויאלית שעל   שמנסה להריץ את M על הקלט x, ולראות האם M עוצרת..) לפיכך,  .

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

עריכה

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

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

טענה:

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


הוכחה: קבוצת השפות הנה למעשה קבוצת כל תתי הקבוצות של  . עוצמת קבוצה זו היא  .

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

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

 

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

 

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

 

כלומר, אם המילה   נמצאת ב־  אז היא לא ב־D. אך אם אינה ב־  אז היא כן תהיה ב־ . ניתן לרשום זאת בצורת טבלה בה כל שורה היא אחת השפות   וכל עמודה היא אחת המילים   נסמן 1 אם   ו־0 אחרת.

 

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

 

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

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


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