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