תורת החישוביות/כריעות שפות/משפט רייס/תרגילים: הבדלים בין גרסאות בדף

תוכן שנמחק תוכן שנוסף
Atavory (שיחה | תרומות)
Atavory (שיחה | תרומות)
שורה 25:
הראה את הכרחיות התנאי הראשון ל[[תורת החישוביות/כריעות שפות/משפט רייס#מניה רקורסיבית של שפות בעלות תכונה|היות החלטת תכונה ב-<math>RE</math>]]. דהיינו, הראה שאם התנאי הבא '''אינו''' מתקיים:
<center>
אם <math>L_1L' \in S</math>, וכן <math>L_1L, L_2L' \in RE</math>, וכן <math>L_1L' \subseteq L_2L</math>, אז <math>L_2L \in S</math>
</center>
אז <math>L_S \notin RE</math>.
 
הנחיה: הראה שאם התנאי אינו מתקיים, אך <math>L_S \notin RE</math>, אז אפשר לכל מ"ט <math>M</math> ומחרוזת <math>x</math> להכריע האם <math>M</math> מקבלת את <math>x</math> (כלומר, להכריע את בעיית העצירה).
 
נניח ש-<math>M_1M'</math> ו-<math>M_2M</math> הן המ"ט של <math>L_1L'</math> ו<math>L_2L</math>, בהתאמה. בנה את המכונה הבאה <math>Q</math>. בהנתן קלט <math>w</math>, המכונה פועלת בשני שלבים.
בשלב הראשון, המכונה מריצה "במקביל" את <math>M</math> על <math>x</math> ואת <math>L_1L'</math> על <math>w</math>:
# בלולאה, היא מריצה מונה <math>i = 0, 1, 2, \ldots</math>
# עבור כל אינדקס <math>i</math>, היא מריצה <math>i</math> צעדים של <math>M</math> ו-<math>i</math> צעדים של <math>L_1M'</math>.
אם במהלך השלב הראשון <math>M_1M'</math> מקבלת את <math>w</math>, המכונה תחזיר תשובה חיובית. אחרת, היא תמשיך לשלב השני.
 
בשלב השני, המכונה מריצה את <math>L_2M</math> על <math>w</math>, ומחזירה את תשובתה.
 
==הכרחיות תנאי 2 למניה רקורסיבית של שפות בעלות תכונה==