תורת החישוביות/כריעות שפות/משפט רייס: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
קט' |
תיקון שגיאת כתיב קטנטנה |
||
שורה 51:
היות ש־<math>S</math> אינה טריוויאלית, בהכרח קיימת שפה <math>L_0</math> כך ש־<math>L_0 \in S</math>. מכיוון ש־<math>S</math> היא קבוצה של שפות ב־<math>RE</math>, גם <math>L_0 \in RE</math>, ונניח כי <math>M_0</math> היא מ"ט המקבלת אותה.
נגדיר מ״ט <math>M_x</math> הפועלת כך:
# מריצה את <math>M</math> על <math>x</math> (ומתעלמת מהתוצאה), ואז
# מריצה את <math>M_0</math> על <math>w</math>, ומקבלת/דוחה כמותה
|