תורת החישוביות/משפט הרקורסיה: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
מ ←אי־כריעות: תיקון |
מ ←אי־כריעות: עקביות |
||
שורה 83:
משפט הרקורסיה מאפשר לנו להניח שהמ״ט בה אנו מתעניינים, יכולה לגשת לקידוד של עצמה. עובדה זו מאפשר "הפניה עצמית" בצורה קלה ונוחה, ויש לה השלכות רבות.
===אי־כריעות===
נוכיח, בעזרת משפט הרדוקציה שהשפה <math>L_\text{HP}</math> אינה כריעה.
{{הוכחה|נניח, בשלילה, ש־<math>L_\text{HP}</math> כריעה והמכונה <math>M</math> מכריעה אותה. נבנה מכונה חדשה <math>CONT</math> באופן הבא.{{ש}}
<math>CONT</math> על הקלט <math>w</math>:
# בעזרת משפט הרדוקציה, <math>CONT</math> כותבת על סרט הזיכרון את <math>\langle CONT \rangle</math>.
שורה 91:
## אחרת, CONT עוצרת ומקבלת
קל לראות ש־CONT יוצרת סתירה: הגישה לקידוד שלה <math>\langle CONT \rangle</math> מאפשר לה לגלות, תוך כדי ריצתה, האם היא אמורה לעצור או לא (בהנחה שבעיה זו כריעה!); CONT מתנהגת באופן הפוך למה שהיא "אמורה" להתנהג, ויוצרת סתירה. פורמלית, עבור מחרוזת w כלשהי,
*אם <math>(\langle CONT\rangle,w)\in L_\text{HP}</math>, אזי M תקבל את הקלט, ו־<math>CONT</math> תכנס ללולאה אינסופית על w, בסתירה לכך ש־<math>(\langle CONT\rangle,w)\in L_\text{HP}</math>.
*אם <math>(\langle CONT\rangle,w)\notin L_\text{HP}</math>, אזי M תדחה את הקלט, ו־<math>CONT</math> תעצור ותקבל את w, בסתירה לכך ש־<math>(\langle CONT\rangle,w)\notin L_\text{HP}</math>.}}
הוכחה זו, במובן מסוים, פשוטה וקלה מההוכחה שראינו בפרק [[תורת החישוביות/כריעות שפות/קיום שפות שאינן כריעות|קיום שפות שאינן כריעות]].
{{תרגיל|יישור=ימין
| |||