Игра в имитацию

Спустя некоторое время статья Чёрча все же достигла берегов Европы. Его работа ставила под сомнение возможность публикации статьи Алана, поскольку научные журналы не позволяли печатать одинаковые исследования. Но теория Чёрча отличалась от работы Алана и в некотором смысле была слабее. Он разработал теорию «лямбда-исчислений» и вместе с логиком Стивеном Клини обнаружил, что такая формальную систему можно использовать для перевода всех арифметических формул в единую стандартную форму. Таким образом, доказательство теорем будут представляться в виде преобразований одной строчки символов лямбда-исчисления в другую, при этом согласуясь с определенным набором довольно простых правил. Затем Чёрч представил доказательство, что проблема возможности преобразования одной строки в другую нерешаема в том смысле, что ни одна формула лямбда-исчислений не могла решить подобный вопрос. Обнаружив пример неразрешимой проблемы, Чёрч смог доказать, что изложенный Гильбертом вопрос, стало быть, также неразрешим. Однако далеко не очевидно было то, что «формула лямбда-исчислений» соответствовала понятию «определенного метода». В то время как Чёрч мог предоставить только словесное подтверждение тому, что любой «эффективный» метод вычисления мог быть представлен в виде формулы лямбда-исчисления, устройство Тьюринга казалось понятным и давало ответ на вопросы, оставленные без внимания в теории Чёрча.

Так или иначе, Алану удалось представить свою работу для публикации Лондонскому математическому сообществу лишь 28 мая 1936 года, в связи с чем Ньюман написал письмо Чёрчу: