תורת החישוביות/כריעות שפות/משפט רייס/תרגילים: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
שורה 43:
הראה את הכרחיות התנאי השני ל[[תורת החישוביות/כריעות שפות/משפט רייס#מניה רקורסיבית של שפות בעלות תכונה|היות החלטת תכונה ב-<math>RE</math>]]. דהיינו, הראה שאם התנאי הבא '''אינו''' מתקיים:
<center>
אם <math>
</center>
אז <math>L_S \notin RE</math>.
שורה 49:
הנחיה: הראה שאם התנאי אינו מתקיים, אך <math>L_S \notin RE</math>, אז אפשר לכל מ"ט <math>M</math> ומחרוזת <math>x</math> להכריע האם <math>M</math> מקבלת את <math>x</math> (כלומר, להכריע את בעיית העצירה).
נניח ש-<math>
בשלב הראשון, המכונה <math>Q</math> מריצה את <math>M</math> על <math>x</math> במשך <math>|w|</math> שלבים.
אם במהלך שלב זה <math>M</math> קיבלה את <math>x</math>, אז המכונה <math>Q</math> תחזיר תשובה שלילית. אחרת היא תמשיך לשלב
בשלב השני, המכונה <math>Q</math> מריצה את <math>
==הכרחיות תנאי 3 למניה רקורסיבית של שפות בעלות תכונה==
| |||