מה לא יוכל מחשב לעשות, לעולם? תשובות שסביר שתקבלו לשאלה זו יהיו: מחשב לא יכול לאהוב, ליהנות מבדיחה, להבין אמירה סרקסטית, ובאופן כללי – לא יכול לחשוב כמוני וכמוכם, בני האדם.
לא נכון.
נכון שעדיין אין לנו מושג איך לגרום למחשב לעשות דבר מהדברים הללו, אבל לא מופרך לחלוטין להאמין שביום מן הימים נוכל לעשות זאת. אם תאמרו "המחשב לעולם לא יוכל לעשות זאת" – טענה שאכן נשמעת לעתים, אוכל לענות בפשטות: הוכיחו.
לכאורה, זו אינה דרישה הוגנת במיוחד. איך אפשר להוכיח שמחשבים לא יוכלו אף פעם להתאהב? בעצם, איך אפשר להוכיח שמחשב לא יהיה מסוגל לעשות משהו אף פעם? ואולי מחר ימציאו תוכנה מתוחכמת שתפתור את מה שהיום נחשב לבלתי־אפשרי?
מתברר כי ישנם דברים שמחשב לא יוכל לעשות לעולם, ואין זה משנה כמה מהר הוא יעבוד, כמה זכרון יעמוד לרשותו וכמה צוותי מתכנתים מומחים יכתבו לו תוכניות. קיימים דברים אותם כל דבר הראוי לכינוי "מחשב" לא יהיה מסוגל לעשות – וקיימת לכך הוכחה מתמטית. אותם דברים אינם קשורים לאהבה או לסרקזם, אלא לבעיות מתמטיות; הבעיות הבסיסיות שאנו מצפים ממחשב להתמודד עמן.
כדי לענות על השאלה "איך אפשר להוכיח דבר שכזה?", עלינו לפנות קודם לשאלה בסיסית עוד יותר: "מה זה בעצם 'מחשב"'?
הבעיה הבלתי אפשרית
המושג המודרני של "מחשב" חב חוב גדול לבעיה מתמטית בעלת השם הבלתי־אפשרי כשלעצמו, entscheidungsproblem, ובעברית - "בעיית הכרעה". את הבעיה הציג בשנת 1928 המתמטיקאי הגרמני דויד הילברט, כחלק מה"פרוגרמה" שלו. מטרת הפרוגרמה הייתה ניסוח מדוייק של המתמטיקה כולה. בשנת 1928 עדיין לא היו קיימים מחשבים כפי שאנו מכירים אותם כיום; היו ידועות מספר מכונות שביצעו חישובים בצורה אוטומטית, אבל בניגוד למחשבים של ימינו, לא היה ניתן לתת להן סדרת הוראות שרירותית ("תכנית מחשב") אלא רק להעביר להן נתונים שעליהם ביצעו חישוב ספציפי כלשהו. לדוגמה, המתמטיקאי בלז פסקל בנה מחשבון מכני שיכל לחבר ולחסר, והמתמטיקאי והפילוסוף גוטפריד וילהלם לייבניץ, מממציאי החשבון האינפיניטסימלי, הרחיב את רעיונותיו של פסקל ובנה מחשבון שיכל לבצע את ארבע פעולות החשבון ואף חישוב שורש ריבועי. למרות שמכונות אלו ודומות להן היוו פריצת דרך, הן עדיין היו מוגבלות למדי ומסוגלות לבצע רק את הפעולות הבסיסיות שלשמן נבנו, ולא לבצע חישובים כלליים בצורה אוטומטית.
הרעיון של מכונה שניתן לתכנת הועלה בידי המתמטיקאי צ'ארלס באבג' כבר בחצי הראשון של המאה ה-19, אולם בנייתה לא הושלמה מעולם. הדברים הדומים ביותר למחשבים שנבנו בפועל היו נול אריגה שהומצא בשנת 1801 וייחודו היה בכך שדוגמת האריגה שלו נקבעה בידי כרטיסים מנוקבים, ומכונה נוספת המבוססת על כרטיסים מנוקבים ששימשה את המשרד האמריקאי לרישום אוכלוסין.
דויד הילברט
אם כן, הבעיה המתמטית אותה ביקש הילברט לפתור לא דיברה בצורה מפורשת על מחשבים. הילברט, מהמתמטיקאים הבולטים של תחילת המאה העשרים, חיפש תהליך חישובי שיהיה מסוגל להכריע עבור טענות מתמטיות האם הן נכונות או שקריות. השאלה האם התהליך יתבצע בידי אדם או מכונה הייתה משנית בחשיבותה.
כמובן שיש לחדד מעט את האתגר שהציג הילברט. טענות כמו "יום יפה היום" אינן בהכרח נכונות או שקריות, וגם טענות בעלות ערכי אמת או שקר ברורים יכולות להיות בעייתיות אם אינן מנוסחות בצורה פורמלית. הילברט הגביל את שאלתו רק לטענות שמנוסחות בלוגיקה מסדר ראשון – פורמליזם מתמטי, שזה לא המקום להכנס לפרטיו פן נאבד את הקוראים הבודדים שעוד נותרו לנו.
אתגר מרכזי בפתרון הבעיה שהציג הילברט היה הצורך לתאר בצורה פורמלית את המושג המופשט של "תהליך חישובי", או בשמו המקובל כיום: "אלגוריתם". אלגוריתם מתואר כסדרת פעולות המתבצעות על קלט מסויים, וגורמות ליצירת פלט מסויים. מתכון לעוגה הוא למעשה דוגמא פשוטה לאלגוריתם: הקלט הוא החומרים שמהם מכינים את העוגה, האלגוריתם הוא תיאור הפעולות שיש לבצע על הרכיבים באמצעות עזרי המטבח, והפלט הוא העוגה עצמה. על עזרי המטבח שבאמצעותם מכינים את העוגה (למשל המיקסר), ועל הטבח עצמו, ניתן לחשוב כעל ה"מחשב" שמריץ את האלגוריתם.
ספר אלגוריתמים ישראלי מוכר
כמובן שבתיאור של מתכון לעוגה ישנן רמות פירוט שונות: האלגוריתם הפשוט ביותר הוא "קח את הרכיבים והכן מהם עוגה". זה אלגוריתם שיכול לפעול על מכונה מתוחכמת דיה (כמו טבח מנוסה). עם זאת, הוא חסר תועלת למדי אם אנו מנסים לנתק ככל הניתן את הקשר שבין האלגוריתם ובין המכונה הספציפית שתפעיל אותו. לכן הדרישה הבסיסית (והחשובה ביותר) מאלגוריתם היא שהוא יהיה מורכב מסדרה סופית של צעדים שכל אחד מהם הוא פשוט מאוד בפני עצמו. כאשר מדובר בתהליך של חישוב, כלל אצבע סביר לקביעה מתי צעד הוא פשוט הוא "כל פעולה שניתנת לביצוע בידי אדם ממוצע עם נייר, עפרון ומספיק זמן". אחרי הכל, האם אדם יכול לגרום למכונה לבצע צעד חישוב שהוא בעצמו אינו יודע כיצד לעשות?
יש עוד דבר בסיסי שהגיוני לדרוש מאלגוריתם: שיעבוד! אם בסיום האלגוריתם לא נקבל עוגה אלא דווקא סלט חסה, כנראה שמשהו משובש באלגוריתם (או לחלופין, משהו משובש – מאוד, אפילו – בטבח). לכן, על־פי־רוב המדד למוצלחותו של אלגוריתם הוא השאלה האם הוא מסתיים תמיד עם התוצאה הרצויה, והאם הוא מסתיים בכלל. אלגוריתם גרוע עשוי שלא לעצור לעולם; למשל, אלגוריתם להכנת עוגה שאומר "הכנס את העוגה לתנור והמתן" יכול להימשך לנצח אם מפרשים בצורה ליברלית את הוראת ההמתנה.
מספר מודלים מתמטיים שונים הוצעו בנסיון לתאר את מושג ה"אלגוריתם". בינתיים, בשנת 1931, ספגה הפרוגרמה של הילברט מכה קשה עם פרסום משפטי האי־שלמות של גדל. ניתן להניח שהוכחתו של גדל השפיעה על מתמטיקאי אחר, אלן טיורינג, שפרסם ב-1936 מאמר שבו הציע מודל מתמטי עבור אלגוריתם, והראה כי ישנן בעיות שאותן המודל אינו מסוגל לפתור (ובכך הנחית – שוב – מהלומה על הפרוגרמה של הילברט). בניגוד להוכחתו של גדל, שהיא מורכבת למדי ודורשת הבנה בלוגיקה, המודל של טיורינג הוא פשוט למדי, וגם ההוכחה שקיימות בעיות שאותן הוא אינו יכול לפתור אינה מסובכת. לימים ייקרא המודל "מכונת טיורינג".
אלן טיורינג
האל מתוך המכונה
מכונת טיורינג אינה באמת מכונה. היא מודל מתמטי מופשט, שמטרתו לייצג את מושג ה"חישוב" בצורה פורמלית וחד־משמעית מחד, ופשוטה ככל הניתן מאידך. למרות שאין זה המודל היחידי (ואף לא הראשון) שעושה זאת, הוא ככל הנראה המפורסם מכולם, ואולי גם האינטואיטיבי ביותר להבנה.
הרעיון הבסיסי פשוט: אנו מדמים את מכונת הטיורינג כמכשיר המורכב מ"ראש" קורא וכותב הנמצא מעל לסרט נייר, שיכולים להופיע עליו התווים 0 ו-1 – קצת בדומה ל"ראש" הקורא והמקליט של נגן קלטות, הנמצא מעל סרט מגנטי. בכל רגע מסוגל הראש לקרוא רק תו אחד מתוך הסרט. על־פי מה שקרא, הוא יכול לשנות את האות שמופיעה במקום הנוכחי ("לכתוב" על הסרט), ולהזיז את הראש צעד אחד ימינה או שמאלה על גבי הסרט, אל האות הבאה או הקודמת. פעולותיו של הראש נקבעות על פי מצבים פנימיים שבהם נמצאת המכונה; בכל צעד חישוב היא יכולה לשנות גם את המצב הפנימי שלה בהתאם למצב הפנימי הנוכחי ולמידע שהיא קראה מהסרט.
המכונה מתחילה את פעולתה כאשר על הסרט כתוב דבר מה – מילת הקלט. היא מסיימת את פעולתה על ידי מעבר למצב פנימי מיוחד המציין את סיום פעולתה, והמידע שכתוב על הסרט באותו הרגע הוא הפלט שלה. התאמה כזו, שבה לכל מילת קלט מותאמת מילת פלט, נקראת פונקציה. לכן ניתן לחשוב על מכונת טיורינג כעל מכונה לחישוב פורמלי של פונקציה מסויימת.
זה הכל.
דוגמה למכונת טיורינג בסיסית ביותר היא מכונה שמקבלת מספר ומכפילה אותו פי 10. לצורך פשטות אפשר להניח שעל סרט המכונה יכולות להופיע כל הספרות מ-0 ועד 9. במקרה זה, כדי לכפול מספר ב-10 כל מה שצריך לעשות הוא להוסיף אפס בסופו; כך למשל את המספר "1234" מכפילים פי עשר על ידי הפיכתו למספר "12340".
מכונת הטיורינג שמבצעת את ההכפלה מורכבת משני מצבים בסיסיים: האחד עוסק בחיפוש אחר סוף הקלט, והאחר מודיע על סיום פעולת המכונה. פעולת המכונה פשוטה: כל עוד היא נמצאת במצב הראשון, היא בודקת מהו הסימן שהיא רואה על הסרט. אם היא רואה ספרה, היא נעה צעד אחד ימינה (קרוב יותר אל סוף המספר). אם לעומת זאת היא רואה תא ריק של הסרט, היא מבינה שהגיעה אל סוף המספר, ולכן היא כותבת 0 בתא הריק ועוברת למצב הפנימי שמודיע על סיום.
איור דמיוני של מכונת טיורינג (באדיבות Schadel)
שתי תכונות חשובות נוספות מאפיינות את המכונה: מספר המצבים הפנימיים שבהם היא יכולה להימצא הוא סופי, ולעומת זאת מתייחסים אל הסרט שאותו היא קוראת ועליו היא כותבת כאל סרט בעל אורך בלתי מוגבל, "אינסופי".
האם זהו מחשב? עדיין לא. יותר נוח לחשוב על מכונת טיורינג כעל תוכנית מחשב – גם תוכנית מחשב מקבלת קלט מסויים ומוציאה פלט מסויים לאחר תהליך חישובי. כדי שניתן יהיה להגיד על מכונת טיורינג שהיא מדמה מחשב, עלינו להראות שהיא מסוגלת "להריץ תוכניות". כלומר, לקבל כחלק מהקלט שלה תוכנית מחשב, ולהריץ אותה על שאר הקלט.
מתברר כי ניתן לעשות זאת. עבור אלגוריתמים שונים (כמו הכפלה בעשר) ניתן לתכנן מכונות טיורינג שונות; אולם טיורינג עצמו כבר הראה כי ניתן גם לתכנן "מכונת טיורינג אוניברסלית", שתהיה מסוגלת לקבל קידוד של מכונת טיורינג אחרת כלשהי בתור חלק מהקלט, ולדמות את ריצתה של מכונה זו על שאר הקלט. מכונת הטיורינג האוניברסלית הזו היא המכונה שמסוגלת לעשות כל מה שמחשב בן זמננו מסוגל לעשות – ואף יותר מכך, שכן הסרט שלה אינו מוגבל בגודלו, בניגוד לזכרונות המחשבים הקיימים כיום.
לא ניכנס כאן להסברים טכניים ארוכים. כדי להשתכנע במידה זו או אחרת שהרעיון של מכונת טיורינג אוניברסלית אינו מופרך מיסודו, די שנשים לב לכך שמכונת טיורינג מאופיינת לחלוטין על ידי אוסף המצבים (הסופי) שלה וההוראות שקובעות עבורה מה לעשות בכל אחד מהם, ואת כל הפרטים הללו ניתן לקודד. כדי להשתכנע בכך שמכונת טיורינג מסוגלת לעשות כל מה שמחשב יכול, נשים לב לכך שגם המחשבים המתוחכמים והחזקים ביותר של זמננו עדיין מבוססים על אוסף קטן למדי של פעולות יסוד, שמזכירות את פעולותיה של מכונת טיורינג: בדוק תא בזכרון, שנה את תוכנו, בצע פעולה אריתמטית כלשהי, וכדומה. את כל פעולות היסוד הללו אפשר לדמות במכונת טיורינג באופן ישיר למדי. כל חישוב שיכול מחשב מודרני לבצע ניתן לביצוע גם בעזרת מכונת טיורינג האוניברסלית.
ניתן להציע שיפורים רבים למודל הפשוט והבסיסי הזה: למה להסתפק בסרט אחד להחזקת נתונים כשאפשר לעבוד עם עשרה? למה להשתמש רק באפסים ואחדות כסימנים על הסרט ולא בכל האלף בית, או בספרות מ-0 עד 9, כמו בדוגמה של המכונה שכופלת ב-10? למה לקפוץ רק צעד אחד על הסרט בכל פעם, ולא ארבעה או חמישה אם מתחשק? ולמה לא להוסיף תאי זכרון נפרדים שבהם המכונה יכולה לאגור מידע מבלי שתצטרך לטייל על הסרט בכל פעם כדי לקרוא אותו? ניתן לעשות את כל הדברים הללו, אך מתברר כי התוצאה תהיה מכונה שקולה מבחינת כוח החישוב. כלומר, כל דבר שמכונת הטיורינג ה"משופרת" תוכל לחשב, גם מכונת הטיורינג המקורית תוכל, למרות שאולי ידרש לה זמן רב יותר. אך כזכור, זמן הביצוע אינו שיקול מבחינתנו לעת עתה: אנו מעוניינים לדעת אם בעיות מסוימות אינן ניתנות לפתרון כלל, גם בהנתן זמן רב מאוד. לשאלת זמן הריצה נידרש במאמר המשך.
כאמור, מכונת טיורינג לא הייתה המודל היחיד שהוצע בנסיון למדל את תהליכי החישוב האוטומטי. מודל שהוצג עוד לפניה הוא תחשיב הלמבדא של אלונזו צ'רץ'. תחשיב הלמבדא מתמטי יותר באופיו ואינטואיטיבי פחות להבנה מאשר מכונת טיורינג, אך ניתן להראות כי שניהם שקולים לגמרי מבחינת יכולת החישוב שלהם – כל פונקציה שניתנת לחישוב על ידי תחשיב הלמבדא ניתנת לחישוב גם על ידי מכונת טיורינג, ולהפך. מודלים חישוביים נוספים שהוצעו התגלו גם כן כשקולים למכונת טיורינג. העובדה שמודלים כה רבים, שהגיעו מחוקרים שונים שעבדו בשיטות שונות אבל כיוונו לאותה המטרה, התגלו כולם כשקולים זה לזה הייתה (ועודנה) הגורם המצדיק את הקביעה לפיה מכונת טיורינג מסוגלת לפתור כל בעיה שניתנת לפתרון אלגוריתמי. הקביעה הזו, שנשמעת בעייתית מאוד בשמיעה ראשונה, מכונה בשם "התיזה של צ'רץ' וטיורינג".
חשוב לציין שגם המחשבים האמיתיים של ימינו, כמו זה שעל מסכו אתם קוראים מאמר זה, הוכחו כשקולים למכונת טיורינג – אין חישוב שניתן לבצע על מחשב מודרני, ואשר אינו ניתן לביצוע על מכונת טיורינג – ולהיפך. אפילו מודל החישוב הקוונטי, למרות שהוא עשוי להוביל לפריצת־דרך מבחינת ביצועי החישוב, שקול מבחינת יכולת החישוב שלו למכונת טיורינג. לכן, אם נראה שמכונת טיורינג אינה מסוגלת לבצע חישוב כלשהו, המסקנה הבלתי־נמנעת היא שגם מחשבים לא מסוגלים לבצעו.
חשוב לציין כי "התיזה של צ'רץ' וטיורינג" אינה משפט מתמטי, ואין לה (וגם לא תהיה לה) הוכחה. הסיבה לכך היא שאין הגדרה מדוייקת למושג כמו "בעיה שניתנת לפתרון אלגוריתמי". למעשה, התיזה מספקת בעקיפין הגדרה כזו: "בעיה אלגוריתמית" היא "כל מה שניתן לחשב באמצעות מכונת טיורינג"... אפשר להניח מספר הנחות סבירות על מהותו של "פתרון אלגוריתמי"; למשל, שהפתרון יכלול שימוש בכמות סופית של זמן וזכרון, ויתבסס על מספר סופי של הוראות בסיסיות שכל אחת מהן בפני עצמה ניתנת לביצוע על ידי מכונה או אדם. אבל לא ניתן לספק הגדרה מדוייקת. בשל כך, אין לנו בטחון מלא שלא יופיע מחר מאן־דהו עם גישה חדשה ומופלאה למושג החישוב, יציע מודל שמכונת טיורינג אינה מסוגלת להתמודד עמו, ויזרוק את התיזה של צ'רץ' וטיורינג לפח. זה אפשרי, אבל לא סביר במיוחד. בימים אלו ממש חוגגת מכונת הטיורינג שבעים שנה להוולדה, וטרם נמצא לה יורש, למרות ההתפתחות האדירה שנעשתה בתחום מדעי המחשב. האם יורש כזה יימצא אי פעם? ימים יגידו. או שלא.
ושמישהו ינסה לעצור אותי
אם כן, עד אשר יבוא מישהו עם הצעה טובה יותר לפירוש המושג "מחשב", אנו (בתקווה) מסכימים שמכונת טיורינג היא המודל שעליו אנו מתבססים בבואנו לדבר על מה שמחשב יכול לעשות. כעת אפשר לחזור לשאלה המקורית: האם קיימות בעיות שאותן מכונת טיורינג אינה מסוגלת לפתור?
כפי שכבר ציינו, התשובה היא כן, ונציג מייד את אחת מהבעיות הידועות ביותר, שהוצגה כבר על ידי טיורינג במאמרו המקורי: בעיית העצירה. בעיית העצירה היא בעיה מתמטית, העוסקת בשאלה מתחום מדעי המחשב – תחום שאינו דורש מהמחשב לגלות בקיאות גדולה באהבה או בסרקזם.
כל מתכנת יודע כמה קל לכתוב (בטעות!) תוכנית שלעולם לא תסיים לרוץ, מכיוון שנקלעה ללולאה אינסופית. דוגמה פשוטה היא זו: נניח שיש לנו תוכנית שמקבלת מספר מהמשתמש ומדפיסה כמספר הזה פעמים "אני אוהב אותך" על המסך. איך יכתוב תוכניתן רשלני את התוכנית? על ידי שמירת משתנה של מספר הפעמים שהשורה הודפסה עד כה על המסך (ערכו של המשתנה יאותחל לאפס), ולולאה שבכל סיבוב שלה מדפיסה את השורה ומגדילה את המונה באחד. בסיום כל סיבוב ריצה של הלולאה, תבדוק התוכנית האם המונה שווה למספר שהתקבל מהמשתמש, ואם כן – התוכנית תעצור. אחרת, היא תמשיך לסיבוב הבא של הלולאה.
התוכנית הזו היא אסון. חשבו למשל מה יקרה אם המשתמש יעביר מספר שלילי בתור קלט: מכיוון שהמונה הוא תמיד מספר חיובי, לעולם לא יווצר השוויון הדרוש לסיום הלולאה, וכך היא תמשיך לעולמי עד (לפחות בתיאוריה). גם הזנה של מספר לא־שלם כקלט תוביל ללולאה דומה. הדרך היחידה לעצור את ריצת התוכנית תהיה על ידי התערבות חיצונית, אם על־ידי עצירה כפויה של התוכנית ואם בעזרת פטיש.
גם בייצוג הפורמלי של מחשבים על ידי מכונות טיורינג אין מנוס מאפשרות הקיום של לולאות אינסופיות. למכונות טיורינג שעלולות לרוץ לנצח על חלק מהקלטים יש חשיבות תיאורטית, אך כאן נתעניין רק בשאלה הבאה: האם קיים אלגוריתם שמקבל קידוד של מכונת טיורינג וקלט עבורה, ומסוגל לקבוע האם המכונה תעצור מתישהו את ריצתה על הקלט הזה – או שלא? (זוהי ה"עצירה" שבשם הבעיה). למעשה, אנו מחפשים לא אלגוריתם, אלא מכונת טיורינג שעונה על השאלה הזו, אך כבר הסכמנו לעת עתה לראות את שני אלה כדברים זהים.
הפתרון המיידי שניתן לחשוב עליו לבעיה זו הוא פשוט: נריץ את המכונה שקיבלנו על הקלט עבורה שקיבלנו, ונראה אם היא עוצרת. אם היא עוצרת, נחזיר תשובה חיובית. אחרת...
כאן אנחנו נתקעים. אם המכונה שאותה אנו מריצים לא עוצרת אף פעם, איך נעצור אנחנו? כמובן, אם ההרצה היא מבוקרת אפשר להניח שאנחנו יכולים לעצור את ההרצה בכל שלב, אחרי שהתייאשנו, ולהחזיר תשובה שלילית. הבעיה היא שכלל לא ברור האם התשובה הזו תהיה נכונה; הרי ייתכן שהמכונה פשוט זקוקה לפרק זמן גדול מאוד, והתייאשנו מהר מדי. הדרך היחידה להשתכנע שהמכונה תרוץ לנצח היא להריץ אותה לנצח, אבל אז לעולם לא נעצור בעצמנו כדי להחזיר את התשובה השלילית.
הנימוק האינטואיטיבי הזה איננו, כמובן, הוכחה לכך שהבעיה בלתי־פתירה; העובדה שאין לנו מושג איך לעשות משהו לא אומרת שאותו דבר הוא בלתי־אפשרי. ההוכחה המדוייקת שהבעיה הזו איננה ניתנת לפתרון אלגוריתמי מתבססת על שיטת הוכחה מקובלת במתמטיקה - הוכחה בדרך השלילה. אנו משחקים ב"מה אם": מניחים שדווקא כן ניתן לפתור את הבעיה, מגיעים מכך לתוצאה אבסורדית, שבה מתקיים דבר והיפוכו, ומסיקים שההנחה שלנו הייתה שגויה.
מכיוון שההוכחה אינה מסובכת, אך יפה מאוד וניתנת להבנה גם בידי אלו שאינם בקיאים בתחום, בחרתי להביא אותה כאן בפירוט.
נניח שקיימת מכונת טיורינג Q המגלמת את האלגוריתם הפלאי שלנו, אשר פותר את בעית העצירה. המכונה Q מקבלת כקלט הגדרה של מכונה טיורינג כלשהי M, ובנוסף קלט I עבור הפעלה של M. המכונה Q מסוגלת, תוך פרק זמן סופי, לחשב ולהגיד האם M עוצרת את ריצתה על הקלט בשלב כלשהו. אם חושבים על אלגוריתם כעל פונקציה, אפשר לאמר כי הפונקציה Q(M,I) תחזיר תשובה חיובית אם המכונה M תעצור על הקלט I, או תשובה שלילית אם המכונה M לעולם לא תעצור על קלט זה.
כעת, נעזר ב-Q על מנת לבנות מכונת טיורינג חדשה, שתוביל לאבסורד. למכונה החדשה הזו נקרא S (אל חשש! כאן סיימנו לסמן דברים באותיות).
הקלט של S הוא פשוט קידוד של מכונת טיורינג כלשהי, M. בתחילת פעולתה, S מפעילה את האלגוריתם הגלום במכונה Q, שכזכור מצפה לשני קלטים - אחד של מכונת טיורינג, והשני של קלט לאותה המכונה. S תעביר את M פעמיים אל האלגוריתם של Q - פעם אחת בתור המכונה ש-Q צריכה לבדוק, ופעם שנייה בתור הקלט שעליו בודקת Q את M. בסימון מתמטי, הצעד הראשון ש-S מבצעת עבור הקלט M הוא החישוב Q(M,M).
זוהי נקודה מבלבלת: מה ש-Q תעשה יהיה להגיד כיצד M מתנהגת כאשר היא מקבלת כקלט את הקידוד של עצמה. כדי להבין כיצד זה אפשרי נזכור שקידוד של מכונת טיורינג, כמו קידוד של כל דבר אחר, הוא פשוט רצף של אפסים ואחדים. איננו יודעים כיצד M תגיב כאשר תקבל את רצף האפסים והאחדים שמהווה את הקידוד של עצמה: ייתכן שהיא תפרש אותו בתור קלט חוקי ותבצע עליו חישוב כלשהו. ייתכן גם שהיא תפסיק מייד את פעולתה ותצהיר "סליחה, תקלה". כמובן, ייתכן גם שהקלט יגרום למכונה לרוץ מבלי לעצור לעולם; ובדיוק במקרה זה אנו מצפים ש-Q תחזיר תשובה שלילית.
חזרה למכונה S. אמרנו שהיא משתמשת ב-Q כדי לבדוק האם M עוצרת על הקלט שהוא הקידוד של M. ההתנהגות של S לאחר הבדיקה הזו תלויה בתוצאותיה. אם Q מחזירה תשובה שלילית, כלומר אומרת כי M לא עוצרת לעולם על הקלט שלה, S תעצור מייד. לעומת זאת, אם Q מחזירה תשובה חיובית, S תיכנס בכוונה ללולאה אינסופית (למשל, בכל צעד חישוב היא תזוז צעד אחד ימינה על הסרט ולא תעשה שום דבר חוץ מזה).
זה כל התיאור של S. עם זאת, נראה כעת כי מכונה S כזו היא אבסורדית בתכלית, וזאת למרות שהבנייה שלה הייתה פשוטה וברורה, תחת ההנחה שקיימת המכונה הפלאית Q שפותרת את בעיית העצירה. נעשה את זה על ידי הדגמת קלט M כלשהו ש-S תקבל, ויגרום לאבסורד של S להיחשף לעיני כל.
כאן מגיע החלק ה"מופרע" ביותר בהוכחה, וגם היפה ביותר: הקלט הבעייתי הזה שאנו מחפשים הוא S עצמה. נשים לב מה קורה כאשר הקלט M ש-S מקבלת הוא בעצמו S: ראשית כל S תעביר את עצמה ל-Q הן בתור המכונה שיש לבדוק, והן בתור הקלט שעליו המכונה רצה. כלומר, יבוצע החישוב Q(S,S). נניח כעת לרגע ש-Q ענתה תשובה חיובית, דהיינו, אמרה ש-S תעצור על הקלט S. במקרה זה, על פי הצורה שבה בנינו את S, מה שתעשה S יהיה להיכנס מייד ללולאה אינסופית, וזאת בסתירה גמורה למה ש-Q זה עתה טענה (ש-S, על הקלט S, עוצרת). אם כך, ברור שלא ייתכן ש-Q תחזיר תשובה חיובית. אם כן נניח כי Q מחזירה תשובה שלילית – כלומר, אומרת ש-S לעולם לא תעצור על הקלט S. במקרה זה (שוב - לפי הצורה שבה בנינו את S), הצעד הבא של S יהיה לעצור מייד, כשהיא שוב שמה ללעג ולקלס את התוצאה שהבטיחה Q.
אם כן, S נמצאת במצב מוזר מאוד: אסור לה לעצור, ואסור לה לא לעצור, כי בכל אחד מהמקרים היא תראה שהמכונה Q טועה! מכאן לא נותר אלא להסיק שלא קיימת שום Q שכזו אשר מסוגלת לפתור את בעיית העצירה. וזוהי ההוכחה כולה.
לב ההוכחה נמצא ברעיון ההפניה העצמית: המכונה S מתייחסת אל עצמה, על ידי כך שהיא מקבלת את עצמה כקלט. יתר על כן, S פועלת על פי מידע שנוגע להרצה הנוכחית שלה, ועושה כמיטב יכולתה להוכיח שהמידע הזה שגוי. למה הדבר דומה? לפרדוקס מוכר העוסק ביכולת לניבוי עתידות. נניח שהגרלת הלוטו היא מעשה כזבים ותמיד נבחרים מספרים שאינם מופיעים באף אחד מהכרטיסים שנקנו, ונניח גם שיש לנו יכולות ניבוי ואנו אף פעם לא טועים. אם ניבאנו מראש מה יהיו המספרים שיופיעו בלוטו, וקנינו כרטיס הגרלה עם מספרים אלו – מה יקרה?
ייתכן שההוכחה נראית בעייתית או מעגלית, אך היא עדיין תקפה לחלוטין מבחינה מתמטית. ברעיונות דומים של הפנייה עצמית השתמש קורט גדל כשהוכיח את משפטי האי־שלמות המפורסמים שלו, ובהם השתמש גם גיאורג קנטור בהוכחתו שלכל קבוצה, גם אינסופית, יש קבוצה גדולה ממנה.
ובכן, ראינו כי קיימת בעיה שאף מכונת טיורינג לא תהיה מסוגלת לפתור לעולם. הבעיה הזו אינה בשום פנים ואופן היחידה; קיימות בעיות רבות שאינן ניתנות לפתרון, מתחומים רבים ושונים, ואף קיימות רמות שונות של "קושי" עבור בעיות שלא ניתנות לפתור, אך לא אוכל להרחיב עליהן כאן. את המתעניינים אפנה לספרו המצויין של דוד הראל, "המחשב אינו כל־יכול" (או לספר טכני ומעמיק יותר שלו, "אלגוריתמיקה").
כריכת ספרו של דוד הראל
האם בני האדם טובים יותר? שאלה טובה. הפיזיקאי והמתמטיקאי רוג'ר פנרוז טוען בספרו "The Emperor’s New Mind" שכן, ומתבסס בטענה זו על תורת הקוואנטים. מצד שני, עדיין אין כל עדות לכך שהדבר נכון והאדם מסוגל לפתור את בעיית העצירה. יתר על כן, קיימות תוכניות רבות שאנו, בני־האדם, איננו יודעים כיום אם יעצרו או לא.
דוגמה פשוטה ניתן להביא באמצעות השערת גולדבך, הטוענת כי כל מספר זוגי הגדול מ-2 ניתן לכתיבה כסכום של שני מספרים ראשוניים. נניח שאנחנו סבורים שההשערה שגויה, ואנו כותבים תוכנית שעוברת על כל המספרים הזוגיים ולכל מספר שכזה מנסה להציגו כסכום כל שני ראשוניים שקטנים ממנו. אם קיימת דוגמה נגדית, התוכנית שלנו תצליח למצוא אותה אחרי פרק זמן סופי. לעומת זאת, אם לא קיימת דוגמה נגדית וההשערה נכונה, התוכנית שלנו תרוץ לעד. אם יכולנו לפתור את בעיית העצירה היינו מסוגלים לומר אם התוכנית תעצור ובפרט אם השערת גולדבך נכונה או לא – שאלה שנותרה פתוחה עד ימינו.
האם די בהבחנה שבין "ניתן לפתרון" לבין "לא ניתן לפתרון"? כלל וכלל לא. לבעיות שניתנות לפתרון יש רמות קושי שונות ומגוונות, וההבדלה ביניהן חשובה אף יותר מההבדלה בין בעיות פתירות לבלתי פתירות. על כך במאמר הבא.
|
קישורים
ה"פרוגרמה" של הילברט - ויקיפדיה
מחשבון מכני פרי יצירתו של פסקל - ויקיפדיה
משפטי האי־שלמות של גדל - מאמרו של אלון עמית על משפט גדל ופירושיו
מודל החישוב הקוונטי - מאמרו של איזי נבו
The Emperor’s New Mind - סקירת הספר, מאת טל כהן
המחשב אינו כל־יכול - סקירת ספרו של הראל, מאת גדי אלכסנדרוביץ'
ההוכחה בחרוזים - מאת ג'פרי פולום
|
RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש