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

31 мая 1936 года

Дорогой Уайт,

Полагаю, вы уже слышали об истории, связанной с работой Тьюринга «О вычислимых числах». Когда статья была уже готова к публикации, появился первый оттиск работы Алонзо Чёрча из Принстона, которому было бы в высшей степени интересно познакомиться с результатами Тьюринга.

Я надеюсь, что несмотря на все обстоятельства работа будет опубликована. Методы в рассматриваемых работах разительно отличаются друг от друга, а результаты исследований настолько важны, что представляют интерес для обеих сторон. Основным результатом работ Тьюринга и Чёрча явилось доказательство, что проблема Entscheidungs, над которой последователи Гильберта трудились многие годы, т. е. проблема нахождения механистического метода решить, является ли указанная строка символов изложением теоремы, доказуемой в рамках аксиоматической системы Гильберта, в общей форме нерешаема.

Тем временем 29 мая Алан отправил очередное письмо матери:

Я только что получил свою готовую и отправленную на публикацию основную статью. Предполагаю, что она появится в октябрьском или ноябрьском выпуске журнала. Относительно Comptes Rendus

возникла сложная ситуация. Как оказалось, тот человек, которому я написал с просьбой передать работу, уехал в Китай. Более того, то письмо затерялось где-то на почте, поскольку второе письмо его дочь все же получила.

Тем временем в Америке появилась статья Алонзо Чёрча, в которой он решил ту же задачу, но другим путем. Тем не менее мы с мистером Ньюманом решили, что предложенный мною метод совершенно не похож на его решение, и это обстоятельство может гарантировать публикацию моей работы. Алонзо Чёрч живет и работает в Принстоне, так что я с уверенностью могу сказать, что отправлюсь туда при первой возможности.

Алан подал зявку на получение стипендии фонда Проктера. Принстон предлагал три возможности: от Кембриджского университета, от Оксфордского университета и от Коллеж де Франс. На стипендию от Кембриджского университета он рассчитывать не мог, поскольку в том году ее уже получил математик и астроном Р. А. Литтлтон. Однако он счел, что средств из стипендии Кингз-Колледжа ему будет достаточно.

Между тем, для публикации работы требовалось предоставить доказательство, что его определение «вычислимого» (computable) числа, т. е. того, что может быть вычислено одной из машин Тьюринга, было тождественно тому, что Чёрч назвал «практически вычислимым», имея в виду возможность описать его формулой лямбда-исчисления. Поэтому он внимательно изучил статью Чёрча, а также его исследования, которые он провел в совместной работе со Стивеном Клини в период с 1933 по 1935 год, и схематически изобразил требуемое доказательство в приложениях к своей работе, которая была готова 28 августа. Аналогичность идей была достаточно очевидна, поскольку Чёрч использовал определение (формулы «нормального вида»), которое соотносилось с определением «удовлетворительных» машин в теории Тьюринга, а затем применил диагональный метод Кантора, чтобы создать неразрешимую проблему.