תורת החישוביות/כריעות שפות/משפט רייס/תרגילים: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
שורה 25:
==הכרחיות תנאי 1 למניה רקורסיבית של שפות בעלות תכונה==
הראה את הכרחיות התנאי הראשון ל[[תורת החישוביות/כריעות שפות/משפט רייס#מניה רקורסיבית של שפות בעלות תכונה|היות החלטת תכונה ב-<math>RE</math>]]. דהיינו, הראה שאם התנאי הבא '''אינו''' מתקיים:
אם <math>L_1 \in S</math>, וכן <math>L_1, L_2 \in RE</math>, וכן <math>L_1 \subseteq L_2</math>, אז <math>L_2 \in S</math>.▼
<center>
▲אם <math>L_1 \in S</math>, וכן <math>L_1, L_2 \in RE</math>, וכן <math>L_1 \subseteq L_2</math>, אז <math>L_2 \in S</math>
</center>,
אז <math>L_S \notin RE</math>
==הכרחיות תנאי 2 למניה רקורסיבית של שפות בעלות תכונה==
| |||