בעיית העצירה.

שלב 1 מתוך 6

עוצרת או לא

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

שלב 2 מתוך 6

הוכחה שהיא לא תעצור

איך יודעים שמכונה לא תעצור? לחכות לא עוזר: אחרי כל מספר צעדים אולי היא תעצור בצעד הבא. צריך סיבה.

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

שלב 3 מתוך 6

מכונה שעצרה

בהבונה העסוק, צעדים שבוצעו עומד על 500, אבל מכונה שעצרה לא ממשיכה לבצע צעדים.

שלב 4 מתוך 6

בודק עצירה

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

שלב 5 מתוך 6

הטיעון של טיורינג

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

שלב 6 מתוך 6

מה זה אומר

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