תורת החישוביות/כריעות שפות/משפט רייס/תרגילים: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
שורה 31:
אז <math>L_S \notin RE.</math>
==הכרחיות תנאי
הראה את הכרחיות התנאי
<center>
אם <math>L_1 \in S
</center>
אז <math>L_S \notin RE
הנחיה: הראה שאם התנאי אינו מתקיים, אך math>L_S \notin RE</math>, אז אפשר לכל מ"ט <math>M</math> ומחרוזת <math>x</math> להכריע האם <math>M</math> מקבלת את <math>x</math> (כלומר, להכריע את בעיית העצירה).
נניח ש-<math>M_1</math> ו-<math>M_2</math> הן המ"ט של <math>L_1</math> ו<math>L_2</math>, בהתאמה. בנה את המכונה הבאה <math>Q</math>. בהנתן קלט <math>w</math>, המכונה פועלת בשני שלבים.
בשלב הראשון, המכונה מריצה "במקביל" את <math>M</math> על <math>x</math> ואת <math>L_1</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_1</math>.
אם במהלך השלב הראשון <math>M_1</math> מקבלת את <math>w</math>, המכונה תחזיר תשובה חיובית. אחרת, היא תמשיך לשלב השני.
בשלב השני, המכונה מריצה את <math>L_2</math> על <math>w</math>.
==הכרחיות תנאי 3 למניה רקורסיבית של שפות בעלות תכונה==
| |||