בעיית העצירה

בעיית העצירה שואלת: האם תוכנית תפסיק לרוץ על קלט מסוים? קלט הוא המידע שמכניסים לתוכנית. אלן טיורינג הראה ב-1936 שאין דרך כללית לבדוק את זה לכל תוכנית וקלט. מכונת טיורינג היא דגם רעיוני של מחשב. ההוכחה משתמשת ברעיון פשוט של סתירה. נניח שיש בודק Halt שמגיד אם תוכנית עוצרת על קלט. נבנה תוכנית A כך:...