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

תוכן שנמחק תוכן שנוסף
יעל י (שיחה | תרומות)
קט'
תיקון שגיאת כתיב קטנטנה
שורה 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>w</math>, המ״ט <math>M_x</math>,
# מריצה את <math>M</math> על <math>x</math> (ומתעלמת מהתוצאה), ואז
# מריצה את <math>M_0</math> על <math>w</math>, ומקבלת/דוחה כמותה