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

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

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

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

במאמרו, לא זו בלבד שטיורינג הגדיר את המכונה והדגים את פעולתה – הוא גם הראה שיש בעיות שמבחינה תיאורטית לא ניתן לפתור באמצעות המכונה הזאת (גם כאשר היא אינסופית!). הדוגמא הבולטת היא בעיית העצירה (שתתואר כאן).

המחשבים המוכרים לנו היום (עשרות שנים לאחר פרסום המאמר האמור!) – הם כולם מימושים סופיים של מכונות טיורינג, ומכאן שהם מוגבלים כפי שהוכח במאמרו הראשוני של טיורינג.