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

 

כעת נקבל מצב אבסורד לגבי הריצה של <math>H'</math> על הקלט <math>x=\langle H'\rangle</math>, כלומר עבור ההרצה <math>H' (\langle H' \rangle)</math>:

# לעומת זאת, אם המכונה איננה עוצרת בהרצה זו, אז בהכרח <math>H(\langle H' \rangle, \langle H' \rangle)</math> החזירה תשובה חיובית (שוב, מפני שהיא השלב הראשון בריצת <math>H'</math> שכתוצאתו הוחלט להיכנס ללולאה אינסופית). אבל לפי ההגדרה של H, משמעות תשובה חיובית זאת היא ש־<math>H' </math> עוצרת על הקלט <math>\langle H' \rangle</math>, וזו שוב סתירה.