Универсальной машине теперь нужно «узнать» еще только две вещи, чтобы сымитировать произвольную машину А: какой символ машина А сканирует в данный момент и в каком положении она находится в данный момент. Третий фокус Тьюринга — это добавление в левой части ленты символа, указывающего текущее состояние, и еще одного символа в правой половине, указывающего, какая ячейка просматривается в данный момент. Четыре компонента информации о произвольной машине А — ее описание, начальные данные, начальное положение и отсканированный в начальной позиции символ — образуют начальные данные для универсальной машины. Вот представление входной ленты U для машины-карточки в перевернутом положении, с исходными данными 5155, первоначально стоящей в позиции сканирования пустой ячейки (0) справа, как на рисунке 3.3:
(шесть правил f) (шесть правил b) (шесть правил F) (шесть правил B) | 000000051550000000
Жирным 0 отмечен сканируемый в начальной позиции символ, а жирным b отмечено начальное положение карточки, то есть указано, какой набор правил использовать. Посмотрите в комментариях на сайте, как на самом деле может выглядеть лента для U.
Разработка такого набора правил для U, чтобы она могла имитировать произвольную машину A, закодированную описанным выше способом на ленте машины U, — долгий и муторный процесс. Суть в том, что U может «видеть» полное описание произвольной машины и полное описание данных для нее. Она может видеть текущее положение произвольной машины и считываемую ею в данный момент ячейку ленты данных. Это полное описание моделируемой машины — на данный момент. Аналогичным образом моделируется следующее положение произвольной машины, и Тьюринг в своей знаменитой статье 1936 года описал U, которая систематически преобразовывала отображение для одного момента в отображение для следующего момента. Таким образом, в процессе моделирования машины-карточки лента U на втором шаге выглядит так:
(шесть правил f) (шесть правил b) (шесть правил F) (шесть правил B) | 000000051555000000
Затем она сымитирует следующий шаг, затем еще один и так далее. Фактическое создание такой конструкции — трудоемкий процесс, но суть его проста. Если вы готовы лишиться девственности (по Хайнлайну), читайте комментарии на сайте, где подробно описан процесс моделирования.
Тьюринг показал, как машина U может имитировать все шаги, проделанные произвольной машиной A. Машине U требуется выполнить много шагов, чтобы смоделировать каждый из них, но это совсем не важно для самого аргумента. U — это универсальный компьютер, потому что он способен вычислять все, что вычисляет любая другая специализированная машина. Просто измените часть описания на ленте U, чтобы изменить вычисляемое.
Тьюринг изобрел программирование. Говоря современным языком, Тьюринг разместил в памяти универсальной машины программу произвольной машины, а также данные для нее — в левой и правой половинах ленты универсальной машины. Чтобы изменить то, какую произвольную машину моделирует универсальная машина и какие вычисления она выполняет, нужно изменить только программу — часть описания в левой половине ленты.
Универсальная машина Тьюринга — это, по сути, то, что мы теперь называем компьютером с хранимой в памяти программой, поскольку она хранит и программу, и данные одинаковым образом — и то и другое находится в однородном пространстве ее памяти. А компьютер с хранимой в памяти программой — это то, что мы называем просто «компьютер». Каждую конкретную машину А, представленную закодированными правилами, мы называем компьютерной программой или просто программой. Теперь вы понимаете, почему программисты часто называют себя кодерами. Они кодируют произвольный алгоритм, реализованный конкретной машиной Тьюринга, в одномерную форму, необходимую компьютеру U. На рисунке 3.5 показано, как универсальная машина Тьюринга U метафорически соответствует современному компьютеру.
Перечислим еще раз, чего добился Тьюринг. Он показал, что может существовать одна-единственная конструкция машины, способная делать все, что представлено систематическими инструкциями. Она не может забивать гвозди или нажимать на клавиши рояля, но она с легкостью исполнит какие-то систематические операции над символами (а вот с помощью полученных результатов — тоже символов — уже можно управлять машиной, которая забивает гвозди или нажимает на клавиши). Чтобы изменить то, что делает машина, нужно лишь изменить ее программу. Тьюринг изобрел концепцию компьютера, под которым мы ныне подразумеваем компьютер с хранимой в памяти программой. Мы реализуем его в виде электронного устройства, чтобы оно работало быстрее.