Чтобы доказать, что такая процедура не может существовать, надо было дать строгое определение термина «эффективная процедура», или «алгоритм», или другого синонима для этого общепринятого интуитивного понятия. Математики в течение столетий не испытывали особых трудностей по этому поводу, поскольку для каждого конкретного бесконечного класса вопросов (то есть для каждой математически определенной функции) было ясно, является или не является алгоритмом процедура, отвечающая на эти вопросы. Однако для того, чтобы показать, что для некоторого бесконечного класса не существует алгоритма, требовалось предварительное уточнение понятия всей совокупности возможных алгоритмов. После этого задача сводится к доказательству, что никакая процедура, соответствующая этому точному определению, не может ответить на все вопросы этого класса.

Ни Тьюринг, ни Ньюмен не знали, что точное определение понятия «эффективной процедуры» уже в течение нескольких лет привлекало внимание Гёделя, Эрбрана, Поста, Чёрча и Клини. К 1936 году было уже предложено три различных по форме определения, а именно: общая рекурсивность Эрбрана – Гёделя, определимость Чёрча – Клини и вычислимость Тьюринга. Все три определения прямо вели к неразрешимости Entscheidungsproblem. В действительности они все эквивалентны.

В 1936 году Клини установил эквивалентность общей рекурсивности и 2-определимости, а Тьюринг приложил к своей работе 1936 года набросок доказательства эквивалентности вычислимости по Тьюрингу и 2-определимости. Далее Чёрч и Тьюринг использовали каждый свою систему для доказательства конкретных результатов, в том числе неразрешимости проблемы распознавания доказуемости в исчислении предикатов.

В следующем году, реферируя работу Тьюринга, Чёрч заметил, что вычислимость с помощью машины Тьюринга «имеет то преимущество, что делает непосредственно очевидным отождествление с эффективностью в обычном (неявно определенном) смысле слова». Вопрос, может ли любая заданная математическая функция в принципе быть вычислена, сводится при этом к вопросу, остановится ли когда-нибудь машина Тьюринга, запущенная с некоторыми входными данными и надлежащей программой вычислений. Соответственно, в нынешней сокращенной формулировке говорят: является ли заданная функция «вычислимой по Тьюрингу»?

Тезис Тьюринга

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

Вычислимость по Тьюрингу

Для построения своего определения Тьюринг начинает с поведения человека, выполняющего заранее указанное вычисление для ответа на некоторый заданный класс вопросов. Он предполагает, что человек имеет конечный набор дискретных состояний памяти и набор точных правил для выполнения чисто механического процесса, использующего конечные ресурсы. Окончание последовательности операций или бесконечное ее продолжение определяет, может ли ответить заданный набор правил на соответствующий вопрос. Введя последовательные упрощения, каждое из которых доказуемым образом не влияет на исход вычислений, он приходит к простому автомату, снабженному бесконечной лентой с последовательностью клеток, в каждой из которых можно поместить символ из некоторого конечного алфавита. Теперь, оставив в стороне человека, можно определить машину Тьюринга для вычисления функции f с помощью конечного множества наборов из пяти символов. Каждый набор может принимать одну из трех форм:

PafiRq, или pafiLq, или pafiNq.

Последовательность таких пятерок интерпретируется как таблица команд для вычисления f. Частное значение аргумента, для которого надо вычислить f (частный вопрос из заданного класса вопросов), вводится в машину как последовательность символов, записываемых в первых n клетках ленты. Команды имеют следующее содержание:

Если машина выполняет команду р и в сканируемой клетке находится символ а, заменить а на в, переключить машину на выполнение команды q и передвинуть ленту на одну клетку вправо, одну клетку влево или оставить её на месте, в зависимости от того, содержит ли данная пятерка соответственно символ R, L или N.

До сих пор для каждой функции f мы должны были строить специализированную машину Тьюринга (Тьюринг называет такие машины «логическими вычислительными машинами» или «ЛВМ»), вкладывая, так сказать, надлежащую таблицу команд в «задний карман» устройства. Предположим теперь, что каждый запуск машины начинает вычисление новой функции f. Тогда можно было бы в каждом случае вначале описать на ленте соответствующую специализированную машину для вычисления f, по существу – ее таблицу команд. Таким образом, можно создать универсальную машину, выполняющую различные команды для вычисления различных функций f, закодированных на ленте. Чтобы привести в действие такую машину, надо вложить в ее «задний карман» новую таблицу команд, на этот раз ведущую таблицу, смысл которой состоит в том, что она определяет язык в виде правил интерпретации.

На языке, несколько более ориентированном на компьютеры, каждая пятерка интерпретируется следующим образом:

 текущая команда p;

 символ а, находящийся в текущей клетке ленты;

 символ в, по условию заменяющий его;

 направление (R, L, N) движения ленты;

 адрес q перехода на следующую команду.

Таким образом, Тьюринг непосредственно связал формальную систему с очевидными устройствами и процессами реального мира и тем самым подготовил теоретические основы для послевоенного развития цифровых вычислительных машин с хранимой программой.

Техническая реализация

Возможность физического осуществления Универсальной машины Тьюринга была в то время далеко не очевидна. Несомненно, ее упустил из виду Джон фон Нейман, который интересовался математическими работами Тьюринга и знал его работу об Entscheidungsproblem. Но, как полагает М.Г.А. Ньюмен в некрологе, опубликованном в Times, сам Тьюринг уже видел эту инженерную возможность: описание, которое он дал тогда «универсальной» вычислительной машине, было, по существу, вполне теоретическим, однако Тьюринг весьма интересовался всевозможными практическими экспериментами и даже в то время рассматривал перспективы практического конструирования машин такого рода.

Этот замысел превратился в конкретный план благодаря приобретенному Тьюрингом в военное время опыту работы с быстродействующими автоматическими счетными устройствами. Работая в Правительственной школе кодов и шифров в Блетчли Парк (Bletchley Park), он стал (вместе с математиком Гордоном Уэлчменом (Gordon Welchman)) идейным руководителем расшифровки немецкого кода для морской связи «Enigma». Они использовали для расшифровки электромеханические устройства, которые назывались «Bombes». В поисках более быстродействующих устройств Тьюринг установил контакт с Т. Флауэрсом (T.H. Flowers), который позже стал главным конструктором серии быстродействующих электронных компьютеров «Colossus». Они предназначалась для криптографического проекта Ньюмена, имевшего другое назначение. Незадолго до смерти Флауэрс рассказывал о своих разговорах за обедом с Ньюменом и Тьюрингом о Чарльзе Бэббидже и его работе. Еще раньше, весной 1943 года, и И. Гуд (I.J. Good), и Д. Мичи