 |
אני אנסה לכתוב את ההוכחה בקצרה תוך שימוש בטרמינולוגיה של תוכניות מחשב ולא של מכונות טיורינג (מכונת טיורינג אוניברסלית שקולה למחשב הניתן לתכנות).
משפט: לא קיימת תוכנית מחשב A אשר מקבלת שני קלטים: תוכנית מחשב Y וקלט x עבור Y, ומחזירה "כן" אם ריצת Y על x עוצרת ו"לא" אם לא.
הוכחה: נניח שקיימת A כזו. נכתוב תוכנית חדשה B המקבלת כקלט תוכנת מחשב Z. התוכנית B מריצה את התוכנית A על הקלטים Y=Z,x=Z. אם הפלט של A על קלטים אלה הוא "כן", התוכנה B נכנסת ללולאה אינסופית. אם התשובה של A היא "לא", התוכנה B עוצרת (ומחזירה, נניח, "כן").
עכשיו בואו נראה האם הרצת B עם Z=B עוצרת או לא. נניח בהתחלה שכן ונתבונן בפרטי החישוב: קודם כל מריצים את A עם Y=B,x=B, כלומר בודקים אם B עוצרת עם Z=B, מכיוון שאנחנו מניחים ש- A פועלת כהלכה, היא צריכה להחזיר "כן" ואז B נכנסת ללולאה ולא עוצרת בסתירה להנחה שלנו.
עכשיו בואו נניח ש- B לא עוצרת על B. במקרה כזה הרצת A אמורה להחזיר "לא" ונקבל ש- B כן עוצרת, שוב בסתירה להנחה.
מכאן שלא קיימת A כפי שהנחנו.
|
 |
RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש