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