Алан Тьюринг был моложе фон Неймана почти на десять лет и приехал в Принстон в 1936 году писать диссертацию по математике. В том же году, за несколько месяцев до поездки в Америку, он в возрасте 23 лет решил величайшую проблему логики – проблему разрешимости. Эта задача восходит к философу XVII века Лейбницу, который мечтал об «универсальном символизме, в рамках которого все логические истины можно будет свести к особого рода расчетам». Но можно ли исполнить мечту Лейбница и свести рассуждения к вычислениям? А точнее, существует ли автоматическая процедура, которая позволила бы решать, следует ли тот или иной вывод из заданного набора посылок? В этом и состояла проблема разрешимости. И Тьюринг ответил на нее отрицательно: он математически доказал, что такой автоматической процедуры не существует. При этом он придумал идеальную машину, которая задавала пределы вычислимости – мы называем ее машиной Тьюринга.
