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

גודלו של עולם הבעיות שאנו פותרים כיום באמצעות מחשב הוא כמעט בלתי נתפס. אם כן, אך טבעי שנשאל: האם יש בעיה כלשהי שמחשב לא יכול לפתור? נבהיר: השאלה היא איננה אם ישנן בעיות שעדיין לא הצלחנו לפתור, או אם ישנן בעיות שתהליך הפתרון אִטי מכדי להיות יעיל, אלא האם ישנן בעיות שבאופן יסודי מחשב לא מסוגל, ולעולם לא יהיה מסוגל, לפתור? בעיות לוגיות מהסוג הזה נפוצות למדי. דוגמה מפורסמת היא "פרדוקס השקרן" במשפט, "המשפט הזה הוא שקר", שמוביל בהכרח לסתירה לוגית פנימית.

כדי לענות על השאלה יש ראשית להגדיר, באופן מתמטי, מהו מחשב ומהי בעיה. מתברר שההגדרה הזו אינה פשוטה כלל. למעשה, חלק ניכר מהגדולה של אלן טיורינג, שנחשב לאחד מאבות מדעי המחשב (אם לא החשוב שבהם) היא בביסוס ההגדרות האלו [1].

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

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

בעיה זו נקראת "בעיית העצירה"[2], והיא בעיה יסודית וחשובה במדעי המחשב. כפי שנראה, התשובה היא שלא קיימת תוכנית H היודעת לפתור זאת. נדגיש שבהרבה מקרים קל להחליט אם תוכנית מסוימת A עוצרת על קלט מסוים. אולם אנחנו טוענים שלא קיימת תוכנית H המסוגלת לענות על השאלה הזו תמיד. במקרה הכללי ביותר - אנו טוענים שלא קיימת H שיכולה להחליט האם A תעצור בפעולתה על קלט x עבור כל תכנית A וכל קלט x.  

ההוכחה שאין תוכנית מחשב כזו היא טיעון לוגי קצר, אך מבלבל להחריד: כדי להוכיח שאין תוכנית מחשב H כזו, נניח על דרך השלילה שכן קיימת תוכנית כזו, ונגיע לסתירה לוגית. נניח כי קיימת תוכנית מחשב H הפותרת את בעיית העצירה. כלומר בהינתן תוכנית A וקלט x עבור A, התוכנית H תמיד עוצרת בפעולתה ועונה אם A הייתה עוצרת בפעולתה על x או לא. כעת נבנה תוכנית חדשה G שמשתמשת ב H כדי לבדוק אם A תעצור כשהיא תרוץ על הקוד של עצמה (ראו איור). 

התכנית G מקבלת קוד של תכנית A כקלט  (ללא קלט x), ומפעילה את H על הזוג A ,A. כלומר שואלת את H האם A עוצרת בפעולתה על הקוד של A. לאחר ש-H עונה אם A עוצרת על הקוד של A (זכרו שהנחנו ש-H תמיד עוצרת), לתוכנית G יש שתי אפשרויות: 

1. אם H ענתה תשובה שלילית -  A אינה עוצרת בפעולתה על A, אז G עוצרת. 
2. אם H ענתה תשובה חיובית - A כן עוצרת בפעולתה על A, אז G נכנסת ל"לולאה אינסופית", כלומר אינה עוצרת (למשל, G יכולה להתחיל פשוט למנות את כל המספרים).

אם נסכם את פעולת G: 

• אם A עוצרת בפעולתה על A, אז G אינה עוצרת בפעולתה על A
• אם A אינה עוצרת בפעולתה על A, אז G עוצרת בפעולתה על A

הבנייה של G אולי נראית תמוהה (מה יש ל A לעשות עם הקוד של עצמה?!), אבל הנקודה היא שזו בנייה אפשרית, בהינתן שהתוכנית H קיימת. כעת למהמורה המבלבלת האחרונה: נשאל את השאלה הפשוטה הבאה - האם G עוצרת בפעולתה על הקוד של עצמה?

ובכן, נשתמש בסיכום לעיל (ונחליף A ב-G), ונקבל ש: 

• אם G עוצרת בפעולתה על G, אז G אינה עוצרת בפעולתה על G. אבל הרי זו סתירה לוגית!
• אם G אינה עוצרת בפעולתה על G, אז G עוצרת בפעולתה על G. אבל גם זו סתירה לוגית!

כך שבכל מקרה, עצם הקיום של התוכנית G מוביל לסתירה לוגית, ומכאן גם ההנחה שלנו על הקיום של H מובילה לסתירה לוגית, כלומר לא קיימת מכונה H הפותרת את בעיית העצירה.

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

מקורות וקריאה נוספת:

[1] Turing, A.M., 1936. On computable numbers, with an application to the Entscheidungsproblem. J. of Math, 58(345-363), p.5.

[2] Davis, M., Computability and Unsolvability, New York, 1958. McGill University.