תורת החישוביות/כריעות שפות/משפט רייס/תרגילים: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
שורה 25:
הראה את הכרחיות התנאי הראשון ל[[תורת החישוביות/כריעות שפות/משפט רייס#מניה רקורסיבית של שפות בעלות תכונה|היות החלטת תכונה ב-<math>RE</math>]]. דהיינו, הראה שאם התנאי הבא '''אינו''' מתקיים:
<center>
אם <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>
בשלב הראשון, המכונה מריצה "במקביל" את <math>M</math> על <math>x</math> ואת <math>
# בלולאה, היא מריצה מונה <math>i = 0, 1, 2, \ldots</math>
# עבור כל אינדקס <math>i</math>, היא מריצה <math>i</math> צעדים של <math>M</math> ו-<math>i</math> צעדים של <math>
אם במהלך השלב הראשון <math>
בשלב השני, המכונה מריצה את <math>
==הכרחיות תנאי 2 למניה רקורסיבית של שפות בעלות תכונה==
|