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

תוכן שנמחק תוכן שנוסף
Atavory (שיחה | תרומות)
Gran (שיחה | תרומות)
שורה 91:
## אחרת, CONT עוצרת ומקבלת
קל לראות ש־CONT יוצרת סתירה: הגישה לקידוד שלה <math>\langle CONT \rangle</math> מאפשר לה לגלות, תוך כדי ריצתה, האם היא אמורה לעצור או לא (בהנחה שבעיה זו כריעה!); CONT מתנהגת באופן הפוך למה שהיא "אמורה" להתנהג, ויוצרת סתירה. פורמלית, עבור מחרוזת w כלשהי,
*אם <math>(\langle CONT\rangle,w)\in \text{HP}</math>, אזי M תקבל את הקלט, ו־<math>M'CONT</math> תכנס ללולאה אינסופית על w, בסתירה לכך ש־<math>(\langle CONT\rangle,w)\in \text{HP}</math>.
*אם <math>(\langle CONT\rangle,w)\notin \text{HP}</math>, אזי M תדחה את הקלט, ו‏־<math>M'CONT</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> אינה כריעה
שורה 102:
## אם R דוחה, <math>M'</math> כותבת את <math>\langle M'\rangle</math> על הסרט (בתור הפלט) ומסיימת.
}}
 
===משפט האי־שלמות של גדל===
{{להשלים}}