Игра в имитацию - Эндрю Ходжес (2015)

Я встретил мистера Ньюмана спустя четыре дня после нашей последней встречи. Сейчас он занят своими исследованиями в других областях и поэтому не сможет уделить должного внимания моей теории на этой неделе. Тем не менее он изучил мои заметки относительно C.R. и после некоторых изменений все-таки одобрил. Позже один французский специалист проверил работу и выслал на публикацию. Однако, я так и не получил подтверждение, и нахожу этот факт весьма досадным. Не думаю, что полный текст работы будет готов за две недели или около того. Скорее всего, ее объем будет превышать пятьдесят страниц. Довольно трудно решить, какие тезисы лучше изложить в статье сейчас, а какие — оставить до следующего удобного случая.

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

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

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

31 мая 1936 года

Уважаемый Профессор Чёрч,

Тот отдельный оттиск вашей статьи, что вы любезно прислали мне на днях, в которой вы исследуете предмет «вычислимых чисел» (calculable numbers) и тем самым доказываете неразрешимость проблемы Entscheidungs Гильберта, представляет весьма мучительный интерес для одного молодого человека, А. М. Тьюринга, который как раз собирался представить для публикации свою работу, с той же целью использующую подобное определение «вычислимых чисел» (computable numbers). Суть его метода состоит в описании устройства, способного произвести вычисление любой вычислимой последовательности, и потому его объяснение качественно отличается от представленного вами, что не умаляет его заслуги. В связи с этим мне кажется важным, чтобы он приехал для совместной работы с вами в следующем году, если существует такая возможность. Вместе с письмом по воле автора высылаю машинописный текст его статьи для ваших замечаний.