В машине Тьюринга нет ничего сложного, верно? На самом деле именно этого и добивался ученый. Он хотел, чтобы его машина была максимально простой (но не проще, перефразируя Эйнштейна). Позже Тьюринг и его бывший учитель, Алонзо Черч сформулировали тезис Черча – Тьюринга, согласно которому задача, которая не может быть решена машиной Тьюринга, не может быть решена никакой другой машиной. Хотя собственно машина Тьюринга способна выполнять крайне ограниченное количество команд и одновременно обрабатывает всего один бит, она может вычислить все, что может вычислить любая вычислительная машина.
Строгие интерпретации тезиса Черча – Тьюринга предполагают принципиальную эквивалентность того, что человек может думать или знать, и того, что может быть вычислено машиной. Основная идея заключается в том, что человеческий мозг подчиняется естественным законам; следовательно, его способность обрабатывать информацию не может превосходить таковую у машины (и соответственно у машины Тьюринга).
В своей статье Тьюринг заложил теоретические основы машинных вычислений. Хотя это целиком и полностью его заслуга, важно отметить, что большое влияние на него оказала лекция, прочитанная Джоном фон Нейманом в 1935 году в Кембридже (Англия). Лекция была посвящена идее программы, которую можно хранить в памяти – концепция, позднее воплощенная в машине Тьюринга. На фон Неймана в свою очередь произвела глубочайшее впечатление статья Тьюринга 1936 года, где были изложены принципы машинных вычислений и которую в конце 1930-х – начале 1940-х годов он включил в список обязательной литературы, составленный для своих коллег.
В той же работе Тьюринг сообщает о другом неожиданном открытии, а именно – о проблеме неразрешимых задач. Неразрешимые задачи – это хорошо описанные задачи с однозначным ответом, который, однако, не может быть вычислен на машине Тьюринга (т. е. на любой машине). Это противоречит постулату XIX века, гласящему, что все задачи, которые могут быть описаны, в конечном счете будут решены. Тьюринг показал, что неразрешимых задач столько же, сколько и разрешимых. В своей «Теореме о неполноте» 1931 года Курт Гедель приходит к аналогичному выводу. Таким образом мы оказываемся в странной ситуации: с одной стороны, мы можем описать задачу и доказать, что однозначный ответ существует, а с другой – знаем, что ответ никогда не будет найден.