|
|
מכאן שאנו יכולים לכתוב את התכנית הדמיונית S בשפה L : בהינתן לה j כקלט , תעבור S על רשימת התכניות ב- , L תמצא את התכנית ה- -jית , ותגיש אותה ואת j כקלט לתכנית Q הפותרת את בעיית העצירה ושאת קיומה אנו מניחים . תוצאות ריצתה של Q יקבעו , כמו קודם ( ראה איור ( , 8 . 8 את המשך פעולתה של : S אם Q תאמר ייכן . ' י תכניט S את עצמה ללולאה אינטופית , ואם Q תאמר " לא S - " תעצור . ואמנם , קל לראות ש- S אכן מתנהגת בדיוק ההפך מאלכטון הטבלה . אולם , מכאן אנו מגיעים לטתירה : הואיל ו- S גם היא תכנית ב- , L והואיל ורשימת התכניות באיור 8 . 9 כוללת את כך התכניות ב- , L אזי חייבת גם S להיות אחת מן התכניות ברשימה . אולם היא אינה יכולה להיות כזאת : אם S היא , למשל , התכנית החמישית ברשימה , היא אינה ~ כולה לעצור על הקלט , 5 היות שבטבלה מופיע " לא" בנקודת המפגש של השורה החמישית והעמודה החמישית . אולם , S על פי בנייתה , כן עוצרת על הקלט , 5 וזוה י טתירה . נהוג לומר שהוכחה זו מתבצעת על-ידי ך'כטון כל התכניות לעומת כל הקלטים , ובניית S להיות היפוך האלכטון . הטתירה היא בכך ש- S היא בלתי אפשרית בתור אחת מתכניות הרשימה...
To the book |
|
|