מכונת טיורינג האוניברסלית

למחשב הדיגיטלי המודרני יש כיום חשיבות רבה

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

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