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

