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

מתוך ויקיספר, אוסף הספרים והמדריכים החופשי
קפיצה לניווט קפיצה לחיפוש

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

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



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

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


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

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

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

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

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

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

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


משפט:

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



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

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

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

אז .

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

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

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

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

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

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

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

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

אז .

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

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

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

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

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

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

אז .

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

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

הגדרה:

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

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