התזה של צ'רץ'

מכונת טיורינג היתה בגדר ניצחון לכל אדם,

 על אחת כמה וכמה לאדם הפועל במבודד, בוגר תואר ראשון בן עשרים ושלוש; אבל טיורינג איבד מיד את יתרונו, בגלל צירוף מקרים מתיש ושכיח בעולם המדע. לפני שטיורינג מסר את מאמרו, הכריז אלונזו צ'רץ' (Church), הלוגיקן הדגול מאוניברסיטת פרינסטון, על מסקנה דומה בעניין ה- Entscheidungsproblem.

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

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