הוכחת בעיית העצירה - המכונה הזדונית נגד אליהו הנביא (ואיך זה קשור לפרדוקס ניוקומב ולתוכנות שמדפיסות את הקוד של עצמן)

בשעה טובה הגענו להוכחה שבעיית העצירה אינה כריעה - כלומר, שלא קיימת מכונת טיורינג, שנסמן באות U, שמקבלת כקלט מכונה M וקלט כלשהו x, ואומרת האם M עוצרת על x.

כמה אנשים איבדתי במשפט הפתיחה הזה?

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

לפני שאתאר את Q, אגלוש אסוציאטיבית לפרדוקס המכונה “הפרדוקס של ניוקומב”. הניסוח פשוט למדי: מראים לכם שתי קופסאות, אחת שקופה והאחת אטומה. בשקופה יש 1,000 שקלים, אבל אין לכם מושג מה יש באטומה. אומרים לכם שמותר לכם לקחת או את הקופסה האטומה בלבד, או את השקופה והאטומה גם יחד, אלא שכמובן שיש עוקץ כאן: על פי מה שמספרים לכם, אתמול בערב ניבא אליהו הנביא האם תיקחו את האטומה בלבד או את השקופה והאטומה גם יחד, ותוכן הקופסה האטומה נקבע על פי הנבואה; אם אליהו ניבא שתיקחו רק את האטומה, הרי ששמו באטומה מיליון שקלים, ואם הוא ניבא שתיקחו את שתי הקופסאות, לא שמו בקופסה האטומה כלום. מה תעשו?

הנחת היסוד של הפרדוקס היא שאליהו הוא נביא אמת ואתם מאמינים שהוא נביא אמת - אחרת, מה אכפת לכם מהנבואות שלו? אם אתם מניחים שהוא נביא אמת יש לכם דילמה: אם תיקחו רק את הקופסה האטומה, יש לכם מיליון שקלים (כי פעלת כפי שמובטח לכם שאליהו ניבא) ואילו אם תיקחו את שתיהן - רק אלף. לכן ברור שכדאי לקחת את האטומה בלבד. מצד שני, מה אליהו כבר יכול לעשות עכשיו, כרגע? הכסף כבר הונח בשתי התיבות, הוא לא יכול לפתע פתאום להיעלם רק כי ברגע האחרון תשנו את דעתכם ותיקחו את שתי התיבות; חבל לוותר כך סתם על אלף שקלים, זה פשוט לא רציונלי. ברור שהדבר הרציונלי לעשות הוא לקחת את שתי התיבות. אבל אז, מובטח שתישארו רק עם 1,000 שקלים! ומצד שני, אם נשארתם עם אלף שקלים, זה אומר שהתיבה האטומה ריקה ואין שום דרך לשנות את זה (כי ההווה לא משפיע על העבר), ולכן כבר עדיף לקחת את שתי התיבות ולהרוויח קצת. וכו’ וכו’ וכו’.

לדעתי הפרדוקס מלמד אותנו שאם קיימת נבואה אמיתית, הרי שבהכרח ההווה צריך להיות מסוגל להשפיע על העבר, או לכל הפחות שלא יהיה קיים שום רצון חופשי. הפרדוקס רומז את זה באופן עקיף למדי, ואפשר להציג זאת באופן ישיר הרבה יותר: נניח שאליהו היה בא אלייך ואומר “המילה הבאה שתגיד תהיה ‘כן’”. מה יקרה? לכאורה, אם יש לך רצון חופשי, אתה יכול להגיד “לא” ולסתור את מה שאליהו - הנביא שתמיד צודק - אמר. לכן לא ייתכן שיהיה לך רצון חופשי, וכו’ וכו’.

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

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

אם U עונה ש-M עוצרת, אז Q נכנסת מייד ללולאה אינסופית. אם לעומת זאת U עונה ש-M לא עוצרת, אז Q עוצר מייד.

וכעת, לפרדוקסליות: איך Q תתנהג על הקלט שהוא Q עצמה?

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

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

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

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

ובינינו, אם תפסתם את אליהו פעם בשקר - תמשיכו לסמוך עליו בעתיד?