ומה הקשר של בעיית העצירה לאלכסון של קנטור?

מי שלא הבין את ההוכחה לאי-כריעות בעיית העצירה, או שהיא סתם לא מעוררת אצלו שום אינטואיציה, אולי יוכל להיעזר בהוכחה “אלטרנטיבית” (במרכאות, כי בפועל עושים בה את אותו הדבר בדיוק) שמהווה וריאציה על שיטת האלכסון של קנטור שכבר הצגתי כאן. זו אחת הדוגמאות הקלאסיות לשימוש בשיטת לכסון במדעי המחשב - יש עוד מספר דוגמאות מעניינות שאולי אביא בעתיד.

הרעיון הוא כדלהלן: כבר אמרנו שכל מכונת טיורינג אפשר לקודד באמצעות מספר טבעי. גם אמרנו שאפשר להניח שהקלטים למכונות הטיורינג הם מספרים טבעיים. לכן אפשר לחשוב על טבלה גדולה, של “התשובה לבעיית העצירה”, שמוגדרת כך: כל שורה מתאימה למכונת טיורינג כלשהי, וכל עמודה לקלט כלשהו. התא (i,j) - השורה ה-i והעמודה ה-j - מכיל “כן” אם המכונה שמספרה i עוצרת על הקלט j, ו”לא” אם היא אינה עוצרת.

שיטת האלכסון של קנטור מבוססת על היטפלות לטבלאות שכאלו, וזה בדיוק מה שנעשה: נגדיר תוכנית חדשה, נניח Q, שמתנהגת “הפוך ביחס לאלכסון” - כלומר, על הקלט 1 היא עושה ההפך ממה שכתוב בתא (1,1), על הקלט 2 היא עושה ההפך ממה שכתוב בתא (2,2), וכן הלאה. די ברור שאותה Q לא יכולה להיות מיוצגת על ידי אף אחת מהשורות בטבלה, כי ההתנהגות שלה שונה מההתנהגות של המכונה שבשורה i לפחות על קלט אחד - הקלט i. מה הולך כאן?

באלכסון של קנטור, האבסורדיות הזו שכנעה אותנו שאי אפשר לכתוב את כל המספרים הממשיים ברשימה ממוספרת - כלומר, יש מספר לא בן מניה של ממשיים. אלא שכאן אי אפשר להסיק את אותו הדבר, כלומר שיש מספר לא בן מניה של מכונות טיורינג; כבר הוכחנו שיש מספר בן מניה שלהן. מה הולך כאן? לכאורה קיבלנו סתירה בסיסית במתמטיקה, משהו בסגנון 0=1, ועוד שתי דקות מטוסים יתחילו ליפול והמחשב המרכזי בבנק שלכם יקרוס.

כמובן שאין כאן שום בעיה - המסקנה היחידה היא שתוכנית כמו Q בכלל לא יכולה להתקיים. אם נגיד “אבל לפני שניה הגדרנו אותה במדוייק ואמרנו איך היא מתנהגת על כל קלט” זה טוב ויפה - אלא שהתעלמנו מכך שהתיאור שנתנו הוא לא אלגוריתם.

שכן מה הולך כאן? אמרנו למכונה Q “על הקלט i תעשי ההפך ממה שכתוב בתא (i,i)”, שזה טוב ויפה, אבל לא אמרנו כלום על איך Q יודעת מה נמצא בתא i. הרי הטבלה שבנינו היא אינסופית; אי אפשר לקודד אותה כחלק מהמכונה Q עצמה, כי כל אלגוריתם הוא סופי (שימו לב עד כמה דרישת הסופיות הזו קריטית).

אם כן, ההנחות הרגילות שאיתן אנו עובדים לא מסייעות לנו ולו ברמז לגלות איך אפשר לכתוב תוכנה מחוכמת כמו Q הזו (אשמח לשמוע הצעות; זה יבשר על חורבן המתמטיקה ונפילת המטוסים המדוברת, אבל זה עדיין יהיה מעניין). כאן נכנסת בעיית העצירה לתמונה: נניח שהייתה איזו מכונה פלאית U שפותרת את בעיית העצירה, אז קיומה היה סולל את הדרך לבניית Q: מה ש-Q הייתה עושה על הקלט i הוא לשאול את U “מה הערך של הכניסה (i,i) בטבלה?” ו-U הייתה עונה, כי זה משמעותה של מכונה שפותרת את בעיית העצירה - שיש לנו דרך אלגוריתמית לדעת מה מכיל כל תא בטבלה. הגענו לסתירה (כי כבר אמרנו ש-Q אבסורדית ולא יכולה להתקיים) ולכן אין שום U פלאית.

בפעם הבאה אעבור מדיבורים על בעיית העצירה עצמה לדיבורים על עוד דברים שהם בלתי כריעים, וההוכחה לכך מתאפשרת בזכות הידיעה שבעיית העצירה בלתי כריעה.