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