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

תוכן שנמחק תוכן שנוסף
Gran (שיחה | תרומות)
Gran (שיחה | תרומות)
שורה 137:
כעת נראה שתנאים אלה מספיקים לכך שההחלטה ב-<math>RE</math>.
{{הוכחה|1=
להלן תיאור מכונה <math>Q</math> המקבלהמקבלת תיאורקידוד מ"טשל מ״ט <math>M</math>, בהכרחובהכרח עוצרת בתשובה חיובית אם <math>L(M) \in L_SS</math>, ולעולם לא עוצרת בתשובה חיובית אם <math>L(M) \notin L_SS</math>. הרעיון הכללי הוא להשתמש ב"הרצה במקביל" ([[w:en:dovetailing|dovetailing]], טכניקת המקבול) הויראטולי (אותהטכניקה כברשכבר ראינו ב[[תורת החישוביות/מודל לבעיות הכרעה#שקילות למודל הכללי|מודל לבעיות הכרעה]]).
 
נשים לב שמתנאי 3 נובע שישנה מכונה <math>Q_3</math> אשר בהנתן שפה סופית השייכת לל־<math>S</math>, עוצרת בשלב כלשהו ומקבלת את השפה. המכונה <math>Q</math> משתמשת ב<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> נתנת למניה רקורסיבית עפ"י(שהרי הבניהזו שפה של מ״ט). מכאן נובע ש-<math>L</math> גם היא ב-<math>S</math>.
}}