תורת החישוביות/כריעות שפות/משפט רייס: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
שורה 137:
כעת נראה שתנאים אלה מספיקים לכך שההחלטה ב-<math>RE</math>.
{{הוכחה|1=
להלן תיאור מכונה <math>Q</math>
נשים לב שמתנאי 3 נובע שישנה מכונה <math>Q_3</math> אשר בהנתן שפה סופית השייכת
▲נשים לב שמתנאי 3 נובע שישנה מכונה <math>Q_3</math> אשר בהנתן שפה סופית השייכת ל<math>S</math>, עוצרת בשלב כלשהו ומקבלת את השפה. המכונה <math>Q</math> משתמשת ב<math>Q_3</math>.
המכונה <math>Q</math> פועלת במספר לולאות מקוננות:
# בלולאה החיצונית ביותר, היא מקדמת אינדקס <math>i = 0, 1, 2, \ldots</math>. עבור כל <math>i</math>, היא מייצרת את המחרוזת ה-<math>i</math> ב[[w:סדר לקסיקורפי|סדר לקסיקורפי]].
שורה 153:
שגם היא ב-<math>S</math>. שיטת הdovetailing כאן מבטיחה שהחל משלב כלשהו, <math>L'</math> תשקל על ידי <math>Q_3</math>. תנאי 3 מבטיח שבזמן סופי כלשהו, <math>Q_3</math> תזהה את <math>L'</math> כשייכת ל-<math>S</math>. שוב פעם, שיטת הdovetailing מבטיחה שלאחר מספיק איטרציות <math>Q_3</math> תפעל מספיק פעמים על <math>L'</math>. כלומר, אם התשובה חיובית, אז <math>Q</math> בוודאות תחזיר תשובה חיובית.
נותר להראות ש-<math>Q</math> לא תחזיר תשובה חיובית במקרה שאיננו נכון. אך נשים לב שזה בדיוק מה שתנאי 1 אומר שאינו קורה: השפה <math>L'</math> היא תת-שפה של <math> L = L(M)</math>, עפ"י בניה. היא שייכת ל-<math>S</math> עפ"י תנאי 3 והעובדה ש<math>Q_3</math> זיהתה אותה. השפה <math>L</math> נתנת למניה רקורסיבית
}}
|