תורת החישוביות/כריעות שפות/משפט רייס/תרגילים

אופטימיזציית מ"טעריכה

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


הפתרון

כדי להמיר זאת לפורמט מתאים לבעיית רייס, נכתוב את התכונה

 

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

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

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


זיהוי שפה ריקהעריכה

נגדיר   מהי התכונה המתאימה למשפט רייס? האם השפה רקורסיבית?

הפתרון

נגדיר את התכונה  , מכילה שפה אחת ולכן אינה טריוויאלית, ולפי המשפט  .


מ״ט המבקרת בכל המצביםעריכה

בהנתן מ"ט   ומחרוזת  , ברצוננו לדעת האם   עוברת בכל אחד ממצביה הלא־סופיים,

 

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

אופטימיזציית מ"טעריכה

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

הכרעת תכונות לא-טריוויאליות איננה נתנת למניה רקורסיביתעריכה

הוכח את המשפט הבא:


משפט:

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


הפתרון

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


הכרחיות תנאי 1 למניה רקורסיבית של שפות בעלות תכונהעריכה

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

אם  , וכן  , וכן  , אז  

אז  .

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

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

  1. בלולאה, היא מריצה מונה  
  2. עבור כל אינדקס  , היא מריצה   צעדים של   ו-  צעדים של  .

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

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

הכרחיות תנאי 2 למניה רקורסיבית של שפות בעלות תכונהעריכה

הראה את הכרחיות התנאי השני להיות החלטת תכונה ב- . דהיינו, הראה שאם התנאי הבא אינו מתקיים:

אם  , אז יש ל-  תת-שפה סופית   המקיימת  

אז  .

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

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

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

הכרחיות תנאי 3 למניה רקורסיבית של שפות בעלות תכונהעריכה

הראה את הכרחיות התנאי השלישי להיות החלטת תכונה ב- . דהיינו, הראה שאם התנאי הבא אינו מתקיים:

שפת כל השפות הסופיות ב-  היא ב-  (כלומר, יש מ"ט המונה כל שפה סופית ב- ).

אז  .

רמז: שים לב שמה שיש להוכיח הוא שאם  , אז כל תת-שפה סופית של יש מ"ט המונה כל שפה סופית ב- .

הרחבת משפט רייס לn-יותעריכה

הגדרה:

תכונה של  -יית שפות ב-  היא קבוצה   של שפות נתנות למניה רקורסיבית מהצורה  . נגיד שתכונה   איננה טריוויאלית אם קיימות שתי  -יות כך ש-  ו- .

  1. הוכח ש .
  2. הראה שבעיית ההחלטה האם שתי מ"ט מקבלות אותה שפה - איננה כריעה.