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

כאשר טיורינג הצטרף, באביב 1935,

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

ההרצאות של ניומן הביאו את טיורינג לנקודה שאליה הגיע גודל (Kurt Godel) במשפט אי השלמות שלו מ- 1931, בטרם היה מפורסם. בעיית היסוד שמשפט זה טיפל בה הייתה כיצד אפשר לתפוס את האמת של טענה על ריבוי אינסופי של מקרים; כך, הטענה שלגבי כל a, b, ו-c, (a+b)c = ac+ab, או הטענה שאין מספר שהוא המספר הראשוני הגדול ביותר. פתרון סביר לכאורה הוא, למשל, לומר שטענות כאלה בכלל אינן חלות על ריבוי אינסופי של מקרים, הן אינן אלא פסוקים סופיים הכוללים מילים כגון "כל", הנגזרים באמצעות כללים רבים, אך במספר סופי, של לוגיקה דדוקטיבית. הלוגיקנים של המתמטיקה ניסו, בשלהי המאה התשע-עשרה, לנסח את הטענה הזאת במפורש, אבל ראסל גילה את הקשיים הבלתי נמנעים הכרוכים במונחים המתייחסים לעצמם (self-referential), והראה כיצד תיאורים סופיים מהסוג "קבוצת כל הקבוצות" עלולים להכיל סתירה עצמית. מאז, המתמטיקאי דייויד הילברט (Hilbert) ניסח דרישות מדויקות יותר מכל מערכת סופית מוצעת באמצעות המונחים המפורסמים : עקביות (consistency), שלמות (completeness) והיות בר-הכרעה (כריעות – (decidebility). ב- 1931 הוכיח גדל שאי-אפשר להשיג במערכת אחת גם עקביות וגם שלמות; יש טענות לגבי מספרים שהן ללא ספק אמיתיות, אולם אי-אפשר להוכיח אותן באמצעות כללים שמספרם סופי על סמך אקסיומות סופיות. גדל התבסס על הרעיון שניתן לקדד טענות על מספרים באמצעות מספרים, ועל בניית טענה המתייחסת לעצמה, וכך מפריכה את תקוותיו של הילברט.