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

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