Через год после выпуска Тьюринг учился в аспирантуре по основаниям математики у Макса Ньюмана; именно там он узнал о программе Гильберта и о ее разрушении Гёделем. Тьюринг понял, что Гёделева теорема о неразрешимости на самом деле говорит об алгоритмах. Вопрос разрешим, если существует алгоритм получения ответа на него. Разрешимость конкретной задачи можно доказать, отыскав такой алгоритм. Понятие неразрешимости глубже, и работать с ним сложнее: необходимо доказать, что таких алгоритмов не существует. Бесполезно и пытаться, если у вас нет точного определения алгоритма. Гёдель, по существу, разобрался с этим вопросом, рассматривая алгоритм как доказательство в рамках аксиоматической системы. Тьюринг же начал размышлять о том, как формализовать алгоритмы в целом.

* * *

В 1935 г. он стал членом Королевского колледжа за независимое открытие центральной предельной теоремы в теории вероятностей, которая обеспечивает некоторое логическое обоснование широкому использованию «колоколообразной кривой», или нормального распределения, в статистическом анализе. Однако в 1936 г., с публикацией основополагающей статьи «О вычислимых числах применительно к Entscheidungsproblem» (проблеме разрешимости), на передний план вышли его мысли о теоремах Гёделя. В этой статье Тьюринг доказал теорему о неразрешимости для формальной модели вычислений, которую сегодня называют машиной Тьюринга. Он доказал, что ни один алгоритм не может решить заранее, остановится ли расчет с получением ответа. Его доказательство проще, чем Гёделево, хотя оба они требуют предварительных ухищрений для организации контекста.

Хотя мы говорим о машине Тьюринга, название это относится к абстрактной математической модели, представляющей идеализированную машину. Тьюринг называл ее а-машиной, где «а» означает «автоматическая». Машину эту можно представить в виде ленты, разделенной на последовательные ячейки, которые могут либо быть пустыми, либо содержать какой-нибудь символ. Лента – это память машины, она ничем не ограничена, но конечна. Если вы подошли к концу, добавьте еще несколько клеток. Некая головка, размещенная над начальной ячейкой, считывает находящийся в ней символ. Затем она сверяется с таблицей, в которой размещены правила перехода (программа, заданная пользователем), записывает в клетку какой-нибудь символ (заменяя им то, что было там до этого) и сдвигает ленту на одну ячейку вперед. Затем, в зависимости от таблицы и символа, машина либо останавливается, либо выполняет инструкции, которые таблица предписывает для символа в ячейке, на которую она передвинулась.

Вариантов существует множество, но все они эквивалентны между собой в том смысле, что могут вычислять одно и то же. Мало того, эта рудиментарная машина способна, в принципе, вычислять все то же, что и цифровой компьютер, сколь угодно быстрый и продвинутый. К примеру, машина Тьюринга, использующая символы 0–9 и, возможно, еще несколько символов, может быть запрограммирована на вычисление числа π до любого заданного числа десятичных знаков, причем машина запишет их в последовательные ячейки ленты и после этого остановится. Такой уровень общности может показаться удивительным для столь простого устройства, но все тонкости вычислений изначально зашиты в таблице с правилами перехода, которые могут быть очень сложными, – в точности как все действия компьютера зашиты в программном обеспечении, которое на нем работает.