תורת החישוביות/כריעות שפות/משפט רייס/תרגילים: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
שורה 47:
אם <math>L_1 \in S,</math>, אז יש ל-<math>L_2</math> תת-שפה סופית <math>L_2 \subseteq L_1</math> המקיימת <math>L_2 \in S</math>
</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>L_1</math>, בהתאמה. בנה את המכונה הבאה <math>Q</math>. בהנתן קלט <math>w</math>, המכונה פועלת בשני שלבים.
בשלב הראשון, המכונה מריצה את <math>M</math> על <math>x</math> במשך <math>|w|</math> שלבים.
אם במהלך שלב זה <math>M</math> קיבלה את <math>x</math>, אז המכונה תחזיר תשובה שלילית. אחרת היא תמשיך לשלב השניה.
בשלב השני, המכונה מריצה את <math>L_1</math> על <math>w</math>.
==הכרחיות תנאי 3 למניה רקורסיבית של שפות בעלות תכונה==
| |||