תורת החישוביות/כריעות שפות/משפט רייס: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
←משפט רייס: שחזרתי להוכחה המקורית, הקודמת לא היתה ברורה כלל (והיו בה הרבה חלקים לא נחוצים) |
|||
שורה 37:
==משפט רייס==
המשפט הבא מראה כי לא ניתן להכריע בעזרת מ״ט האם השפה של מכונה מסויימת מקיימת או לא תכונה לא טריוויאלית S.
{{משפט|תוכן=
לכל תכונה לא טריוויאלית S של שפות ב־RE מתקיים:{{רווח קשיח|10}} <math>L_S \notin R</math>{{רווח קשיח|10}}}}
| |||