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