תורת החישוביות/כריעות שפות/משפט רייס: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
שורה 66:
==תכונות שפות ומניה רקורסיבית==
בחלק הקודם ראינו שאם התכונה <math>S</math> איננה טריוויאלית, אז שאלת השייכות ל-<math>L_S</math> איננה ב-<math>R</math>. בחלק זה נעסוק בשאלה מהם התנאים ל-<math>S</math> כך ששאלת השייכות ל-<math>L_S</math> תהיה ב-<math>RE</math>.
נתחיל בכך שללא תנאים נוספים, אם <math>S</math> תכונה לא טריוויאלית, אז שאלת השייכות ל-<math>L_S</math> איננה ב-<math>RE</math>. ב[[תורת החישוביות/כריעות שפות/משפט רייס/תרגילים#הכרעת תכונות לא-טריוויאליות איננה נתנת למניה רקורסיבית|תרגיל: הכרעת תכונות לא-טריוויאליות איננה נתנת למניה רקורסיבית]] תתבקש להוכיח זאת.
==דוגמאות ליישומים==
| |||