Устройство управления выполняет программу, подчиняясь строгим правилам. В любой момент времени устройство управления находится в некотором состоянии, которое записано в регистре текущее состояние. Состояния обозначаются положительными целыми числами. Каждая команда программы представляет собой пятерку, составленную из состояния, литеры, еще одного состояния, еще одной литеры и направления движения ленты. Цикл выполнения команды начинается с того, что устройство управления сравнивает текущее состояние и литеру на ленте под головкой с первыми двумя компонентами всех команд. По правилам программирования для машины Тьюринга в программе может быть не более одной пятерки с какой-либо определенной начальной парой состояние-литера (но может и не быть ни одной). Когда совпадение найдено, устройство управления выполняет три действия: в ячейку ленты под головкой записывается литера, являющаяся четвертой компонентой пятерки; головка передвигается на одну ячейку влево или вправо или остается на месте, как указано в пятой компоненте пятерки; текущее состояние заменяется на третью компоненту. После этого машина готова к следующему циклу. По соглашению, работа начинается в состоянии 1 при описанном выше состоянии ленты. Машина останавливается, если в цикле выполнения не удается найти совпадения с текущей парой состояние-литера или если головка выходит за левый край ленты; при этом результатом работы считается все, что остается на ленте после остановки. Отметим, что программа может содержать лишь конечное число команд, так что для любой программы осмысленно только конечное число состояний и литер.
Для пояснения изложения полезно привести пример. Пусть мы хотим написать программу для машины Тьюринга, которая будет строить сумму двух целых чисел. Целое число п будет изображаться на ленте n последовательными значками * (отсутствие звездочек соответствует нулю), два исходных числа будут разделены запятой, и если исходные данные представляют n + m, то результатом должны быть n + m звездочек, расположенных у левого края ленты. Так, чтобы вычислить 7 + 4, следует записать в качестве исходных данных
*******,****
результатом должно быть
***********
Структура программы проста. Сначала головка движется вправо в поисках запятой (не забывайте, что первоначально головка стоит над крайней левой ячейкой исходных данных). Запятая заменяется звездочкой, и головка продолжает движение, отыскивая пробел, ограничивающий справа исходные данные. Головка возвращается на одну ячейку назад и записывает пробел на место находящейся там звездочки, после чего программа завершается. Легко видеть, что при построении суммы одна звездочка добавляется в середине и одна убирается с правого края. Программа приведена в табл. 13.1.
Чтобы изобразить состояние машины Тьюринга, можно напечатать все ячейки ленты, которые когда-либо рассматривались, и среди них — текущее состояние непосредственно слева от ячейки, находящейся под головкой в данный момент; такой способ мы будем считать стандартным. Мы получаем моментальный снимок; следующий пример показывает начало сложения 2 и 3:
1**,***
На рис. 13.1 показана последовательность моментальных снимков для всего вычисления. Отметим, что программа останавливается в состоянии 3, поскольку в ней не предусмотрены действия для пробела. Состояние 4 возникает только, если в исходных данных имеется ошибка; в этом случае машина попадает в бесконечный цикл. Убедитесь, что программа работает, если любое из исходных чисел (или оба) равно нулю.
Рисунок 13.1. Последовательность моментальных снимков.
Наш пример программы может показаться слишком простым. Попробуйте изменить программу, чтобы она выполняла не сложение, а умножение. Для машины Тьюринга единичная система счисления более естественна, чем любая другая; программа сложения десятичных чисел будет длиннее и сложнее. В литературе, указанной в библиографии, можно найти гораздо более подробный материал о машине Тьюринга и обоснование того, что машина Тьюринга может выполнить любое вычисление, выполнимое на какой-либо другой машине. Вы обнаружите небольшие отличия в разных описаниях машины Тьюринга и там же — доказательства того, что эти отличия ни на что не влияют.