תורת החישוביות/כריעות שפות/משפט רייס/תרגילים: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
שורה 40:
בשלב השני, המכונה מריצה את <math>L_2</math> על <math>w</math>.
==הכרחיות תנאי 2 למניה רקורסיבית של שפות בעלות תכונה==
הראה את הכרחיות התנאי השני ל[[תורת החישוביות/כריעות שפות/משפט רייס#מניה רקורסיבית של שפות בעלות תכונה|היות החלטת תכונה ב-<math>RE</math>]]. דהיינו, הראה שאם התנאי הבא '''אינו''' מתקיים:
<center>
אם <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>
==הכרחיות תנאי 3 למניה רקורסיבית של שפות בעלות תכונה==
| |||