תורת החישוביות/כריעות שפות/משפט רייס: הבדלים בין גרסאות בדף

תוכן שנמחק תוכן שנוסף
Atavory (שיחה | תרומות)
Atavory (שיחה | תרומות)
שורה 64:
}}
 
==מניה רקורסיבית של שפות בעלות תכונה==
==תכונות שפות ומניה רקורסיבית==
 
בחלק הקודם ראינו שאם התכונה <math>S</math> איננה טריוויאלית, אז שאלת השייכות ל-<math>L_S</math> איננה ב-<math>R</math>. בחלק זה נעסוק בשאלה מהם התנאים ל-<math>S</math> כך ששאלת השייכות ל-<math>L_S</math> תהיה ב-<math>RE</math>.