מכונה שרק קוראת, כותבת וזזה
ב־1936 שאל אלן טיורינג מה פירוש לחשב משהו על ידי מילוי כללים. הוא דמיין פקיד שעובד עם עיפרון ונייר, ופירק את העבודה שלו לצעדים הקטנים ביותר. הפקיד מסתכל בכל פעם על משבצת אחת של הנייר, יכול לכתוב בה סימן או למחוק אותו, יכול לזוז משבצת אחת שמאלה או ימינה, וזוכר בראש רק מעט מאוד: את המצב שלו.
המכונה בסצנה היא הפקיד הזה, בנוי כמכשיר על שולחן עבודה. סרט נייר מחולק לתאים נמתח בין שני סלילים. הראש עומד מעל תא אחד: המנורה שלו קוראת את הסימן שבתא, החותמת שלו יכולה להטביע סימן חדש, והסרט מחליק מתחתיו תא אחד בכל פעם. התצוגה שעל הראש מראה את המצב שלו, אות אחת.
זו כל המכונה. אין לה יחידה אריתמטית, אין לה זיכרון מלבד הסרט ואין לה הוראות מלבד מה שכתוב בכרטיס הכללים. ובכל זאת מתברר שהיא יכולה לבצע כל חישוב שכל מחשב יכול לבצע.
כרטיס הכללים הוא התוכנית
מאחורי הראש עומד כרטיס הכללים. יש בו שורה לכל מצב ועמודה לכל סימן שהראש יכול לקרוא. כל כלל אומר שלושה דברים: איזה סימן לכתוב, לאיזה כיוון לזוז ולאיזה מצב לעבור. צעד הוא תמיד אותו דבר: קוראים את התא, מוצאים את הכלל של המצב הנוכחי ושל הסימן הזה, ואז כותבים, זזים ומחליפים מצב. הכלל שהמכונה תשתמש בו עכשיו מואר.
המחבר מחבר 3 ו־2 שכתובים כקווי ספירה, 111_11. במצב A הוא רץ ימינה על המספר הראשון. ברווח הוא כותב 1, מחבר את שני המספרים לשישה קווים ועובר ל־B. B רץ עד הסוף, חוזר צעד אחד ועובר ל־C, שמוחק קו אחד ועובר לעצירה. למצב העצירה אין שורה בכרטיס, ולכן אין עוד מה לעשות: המכונה נעצרת וחמש אחדות על הסרט.
נסו: בתוכנית בחרו מחבר, החזירו את צעדים שבוצעו ל־0, ואז הזיזו אותו קדימה צעד אחר צעד. עקבו אחרי הכלל המואר בכרטיס ואחרי האות שבתצוגת הראש, וראו את החותמת ממלאת את הרווח בצעד 4 ומוחקת את הקו האחרון בצעד 8.
יש תוכניות שנעצרות ויש שלעולם לא
להריץ תוכנית היא הדרך הברורה לגלות מה היא עושה, אבל היא נותנת רק חצי תשובה.
הבונה העסוק מתחיל על סרט ריק עם שלושה מצבים. הוא נודד הלוך ושוב, כותב שש אחדות ונעצר בצעד 14. טיבור ראדו שאל ב־1962 כמה צעדים יכולה לרוץ מכונה עם מספר מצבים נתון לפני שהיא נעצרת. התשובות גדלות במהירות מגוחכת: השיא לחמישה מצבים, 47,176,870 צעדים, הוכח ב־2024 בשיתוף פעולה גדול ברשת, ולשישה מצבים השיא הוא מספר ארוך מכדי שאפשר יהיה לכתוב אותו.
מכונת הפינג־פונג זזה ימינה וחזרה לעד. אחרי הצעד הראשון שלה היא מראה שוב ושוב את אותן שתי תמונות. מכונה דטרמיניסטית שחוזרת לתמונה שכבר הראתה חייבת לחזור על עצמה לעד, ולכן את זו אפשר לתפוס.
המונה סופר בבינארית: 1, 10, 11, 100 וכן הלאה. הוא אף פעם לא נעצר, וגם אף פעם לא חוזר על עצמו, כי כל סבב משאיר על הסרט מספר גדול יותר. מי שצופה בו 500 צעדים או 500 שנה לומד רק שהוא לא נעצר עדיין.
נסו: החליפו את תוכנית בין ארבע התוכניות והזיזו את צעדים שבוצעו ל־20, ואז עד הסוף, ל־500. המונה שעל שולחן העבודה אומר אם המכונה עצרה או עדיין רצה.
האם תוכנית יכולה לבדוק בשבילנו?
על ארבע התוכניות האלה אפשר לדעת מה יקרה אם חושבים על כל כרטיס כללים. השאלה האמיתית היא אם יש שיטה אחת שעובדת לכל כרטיס. דמיינו מכונה H, בודק עצירה, שמקבלת כל כרטיס כללים ואת הסרט שהמכונה מתחילה ממנו, ותמיד עונה נכון ובזמן סופי: עוצרת או רצה לעד.
H היה מועיל מאוד. מכונה שמחפשת בין המספרים הזוגיים מספר שאינו סכום של שני ראשוניים נעצרת רק אם השערת גולדבך שגויה, ולכן H היה מכריע את הבעיה הפתוחה המפורסמת הזאת אחר צהריים אחד. כך אפשר היה להכריע גם בעיות פתוחות רבות אחרות במתמטיקה.
נסו: הזיזו את ניסיון של בודק עצירה אל בודק עצירה. H לוקח עותק של כרטיס הכללים הטעון ומדליק את התשובה שלו, ובארבעת הכרטיסים האלה הוא צודק.
למה בודק העצירה לא יכול להתקיים
כרטיס כללים הוא בעצמו רק סימנים, ולכן אפשר לכתוב אותו על סרט ולתת אותו כקלט למכונה אחרת, ואפילו למכונה עצמה. טיורינג השתמש בזה כדי להראות ש־H לא יכול להתקיים. נניח שהוא קיים. נבנה מכונה חדשה, D, שמקבלת כרטיס כללים P, שואלת את H אם P נעצרת כשנותנים לה את הכרטיס שלה, ואז עושה את ההפך: אם H עונה „עוצרת”, D מסתובבת לעד; אם H עונה „רצה לעד”, D נעצרת.
עכשיו ניתן ל־D את הכרטיס שלה עצמה. אם H אומר ש־D נעצרת, D מסתובבת לעד, ולכן H טעה. אם H אומר ש־D רצה לעד, D נעצרת, ולכן H טעה שוב. כל תשובה אפשרית שגויה, ולכן ההנחה נופלת: אין מכונה שיכולה להכריע, לכל תוכנית ולכל קלט, אם היא נעצרת. זו בעיית העצירה, והיא בלתי כריעה. הטיעון של טיורינג מ־1936 עסק בתכונה מעט שונה, אבל זו הדרך המקובלת היום לספר אותו.
נסו: הזיזו את ניסיון של בודק עצירה אל אין בודק. הלוח עובר על D שמקבלת את הכרטיס שלה, והמנורות של H לא מצליחות להתייצב על אף תשובה.
מה זה אומר על מחשבים
טיורינג תיאר גם מכונה אוניברסלית: כרטיס כללים קבוע אחד שקורא מהסרט כרטיס כללים של מכונה אחרת ועושה כל מה שהמכונה ההיא הייתה עושה. זה הרעיון שמאחורי כל מחשב מאז, ששומר את התוכניות שלו באותו זיכרון שבו נמצאים הנתונים. אלונזו צ’רץ’ הגיע לאותם גבולות ב־1936 בדרך אחרת, והטענה שהמכונות האלה תופסות את כל מה שאפשר לחשב על ידי מילוי כללים נקראת התזה של צ’רץ’–טיורינג.
לבעיית העצירה יש חברה. משפט רייס אומר שכל שאלה לא טריוויאלית על מה שתוכנית עושה, למשל אם היא תדפיס אי־פעם 7 או אם שתי תוכניות נותנות תמיד אותה תשובה, בלתי כריעה באותו אופן. כלים שבודקים תוכנה ומחפשים באגים או וירוסים עדיין עובדים, אבל הם נאלצים להסתפק בתשובה „כן”, „לא” או „לא ידוע” על חלק מהתוכניות. גם מספרי הבונה העסוק אינם ניתנים לחישוב: אילו אפשר היה לחשב אותם, אפשר היה לפתור את בעיית העצירה על ידי הרצת מכונה מספר כזה של צעדים.
מה המודל הזה משמיט
מכונת טיורינג היא רעיון מתמטי, לא מכשיר; טיורינג מעולם לא בנה אחת, והסלילים, החותמת והמנורה מצוירים כדי להפוך את הרעיון למוחשי. הסרט שלה אינסופי, ואילו לכל מחשב אמיתי יש זיכרון סופי, כך שבעיקרון מחשב אמיתי חייב בסוף לחזור על עצמו. בפועל זה לא עוזר: למכונה עם כמה ג׳יגה־בייטים יש יותר מצבים אפשריים ממספר האטומים ביקום. ארבעת כרטיסי הכללים הם דוגמאות זעירות, כל צעד מואט ומוחלק כדי שאפשר יהיה לצפות בו, והמחוון נעצר ב־500 צעדים אף שהפינג־פונג והמונה לעולם לא נעצרים. בודק העצירה H דמיוני, והלוח מקצר את ההוכחה של טיורינג לעיקר שלה: לתת ל־D „את הכרטיס שלה” פירושו לכתוב על הסרט שלה תיאור של כרטיס הכללים שלה.