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