בעיית העצירה

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

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

אלן טיורינג הוכיח ב-1936 שאין אלגוריתם כללי שמחליט את השאלה הזאת עבור כל תוכנית וקלט. מכונת טיורינג (מודל תאורטי של מחשב עם זיכרון בלתי־מוגבל) שימשה במודל ההוכחה. חשוב: עבור כל תוכנית וקלט התשובה מוגדרת היטב, אבל אין דרך חישובית כללית למצוא אותה תמיד.

ההוכחה פועלת בדרך השלילה: מניחים שיש פתרון לבעיית העצירה ומגלים סתירה לוגית. נניח קיים אלגוריתם Halt(Q,X) שמוחזר אמת אם Q עוצרת על X ודוחה אחרת. נבנה את התוכנית הבאה A(Q):

- אם Halt(Q,Q) מתקיים, A נכנסת ללולאה אינסופית.
- אחרת, A עוצרת.

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

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

בנוסף, יש הוכחה פשוטה אחרת: יש יותר פונקציות אפשריות ממה שיש לתאר בעזרת מכונות טיורינג, ולכן חלק מהפונקציות אינן חישוביות. חלק מהפונקציות האלה לא מעניינות כי אין להן תיאור סופי שימושי.

RE (recursively enumerable) היא קבוצה של שפות עבורן קיימת מכונה שמקבלת כל מילה בשפה, ואינה מקבלת (דוחה או לא עוצרת) מילים שלא בשפה. אפשר לבנות מכונת טיורינג שמריצה את Q על X ומקבלת אם Q עוצרת. לכן בעיית העצירה היא ריצתית־מנית (בתוך RE).

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

בעיית העצירה שואלת: האם תוכנית תפסיק לרוץ על קלט מסוים? קלט הוא המידע שמכניסים לתוכנית.

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

ההוכחה משתמשת ברעיון פשוט של סתירה. נניח שיש בודק Halt שמגיד אם תוכנית עוצרת על קלט.

נבנה תוכנית A כך:

- אם הבודק אומר שהתוכנית Q עוצרת על Q, אז A לא תעצור.
- אחרת A תעצור.

עכשיו שואלים: מה קורה ל-A כשהיא מריצה את עצמה? בכל מקרה נגיע לסתירה. לכן לא יכול להיות בודק כזה.

RE זו קבוצה של בעיות שאפשר לזהות תשובה חיובית להן על ידי הרצה. אם Q עוצרת על X, אפשר להריץ אותה ולגלות את זה.

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