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