מכונת טיורינג.

שלב 1 מתוך 5

קורא, כותב, זז

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

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

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

שלב 2 מתוך 5

למלא את הרווח

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

במצב A המכונה רצה ימינה על האחדות ומשאירה אותן כמו שהן. אחרי שלושה צעדים היא מגיעה לרווח.

שלב 3 מתוך 5

התשובה על הסרט

אחרי שהרווח מתמלא, B רץ ימינה עד התא הריק שבסוף, חוזר צעד אחד ועובר ל־C. ‏C מוחק אחדות אחת ועובר לעצירה: למצב העצירה אין שורה בכרטיס, ולכן אין עוד מה לעשות. מה שכתוב על הסרט ברגע העצירה הוא התשובה.

שלב 4 מתוך 5

לספור צעדים

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

שלב 5 מתוך 5

המצב השלישי

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