תורת החישוביות/משפט הרקורסיה: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
מ ←שימושים: עיצוב, הגהה |
|||
שורה 87:
# המכונה מריצה את M על הקלט <math>(\langle CONT \rangle, w)</math>
## אם M מקבלת את הקלט, CONT נכנסת ללולאה אינסופית
## אחרת, CONT עוצרת ומקבלת
קל לראות ש־CONT יוצרת סתירה: הגישה לקידוד שלה <math>\langle CONT \rangle</math> מאפשר לה לגלות, תוך כדי ריצתה, האם היא אמורה לעצור או לא (בהנחה שבעיה זו כריעה!)
*אם <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> אינה כריעה
שורה 99 ⟵ 100:
## אם R דוחה, <math>M'</math> כותבת את <math>\langle M'\rangle</math> על הסרט (בתור הפלט) ומסיימת.
}}
==לקריאה נוספת==
| |||