§ 13.2. Композиция машин Тьюринга

Как мы убедились в предыдущем параграфе, работа машины Тьюринга однозначно определяется функционированием управляющего устройства в соответствии с основной таблицей. Здесь и далее всегда будем предполагать, что машина начинает работу от определенного начального состояния, обозначаемого символом и всегда имеет состояние покоя , которым заканчивается ее работа. Имея в виду такое соглашение, можно определить операции над машинами Тьюринга, позволяющие по заданным основным таблицам получать новые.

Представим себе, что имеются две машины: . Пусть в начальными момент времени имеется некоторая ситуация на ленте, которую начинает перерабатывать машина отправляясь от начального состояния , причем считывающая и записывающая головка машины находится при напротив некоторой ячейки ленты. Тогда к некоторому моменту машина перейдет в состояние покоя , а головка машины остановится напротив некоторой ячейки. В момент «отключим» машину и представим себе, что с этого момента начинает работать машина , отправляясь от начального состояния , причем головка машины находится в момент напротив той самой ячейки , около которой закончила работу машина . К какому-то моменту времени машина закончит работу, перейдя в состояние покоя , причем головка машины остановится напротив некоторой ячейки . Легко понять, что результат такой последовательной работы машин при любом начальном (при заполнении ленты и положении головки эквивалентен работе одной машины Тьюринга Г, основная таблица которой строится по следующему правилу: если управляющие устройства машин имеют состояний соответственно, то управляющее устройство машины состояний, причем, начальным состоянием машины Т является , а состоянием покоя —

. Основная таблица Т состоит из двух частей: верхняя часть описывает машину нижняя — , причем состояние покоя машины отождествляется с начальным состоянием машины . Пусть, например,

— это машина F из предыдущего параграфа, а — машина G (табл. 13.19 и соответственно). Тогда машина Г имеет таблицу с состояниями — табл. 13.26, где состояние покоя машины .

Если перенумеровать подряд состояния машины Т, то табл. 13.26 примет вид табл. 13.27.

Таблица 13.26

Таблица 13.27

Таблица 13.28

Машину Т, получаемую описанным выше способом из , назовем произведением машин , а саму операцию получения по двум заданным машинам третьей будем называть умножением машин. В этих обозначениях табл. 13.26 и 13.27 представляют собой таблицы машины . Очевидно, умножение машин — некоммутативная операция, т. е. . Например, произведение представлено табл. 13.28, отличающейся от табл. 13.27.

Вместе с тем, как легко понять, умножение ассоциативно, т. е. если имеются три машины , то . Поэтому при записи произведения нескольких машин можно не употреблять скобок.

Обычным образом определяется операция возведения в степень: степенью машины Т называется произведение сомножителями .

До сих пор в этом параграфе шла речь об умножении машин, имеющих одно состояние покоя. В том случае, когда одна из перемножаемых машин имеет два или несколько состояний покоя (например, машины Е и М из предыдущего параграфа), умножение определяется совершенно аналогично, но только обязательно должно присутствовать указание, какое из состояний покоя предыдущего сомножителя отождествляется с начальным состоянием последующего.

Так, например, если машина имеет два состояния покоя, то произведение мы будем обозначать через или через в зависимости от того, отождествляется ли начальное состояние машины с первым или вторым состоянием покоя машины . Машина Т в этом случае также имеет два состояния покоя: первое — одно из состояний покоя , второе — состояние покоя .

Из предыдущих определений ясен также смысл такой, например, записи:

Здесь умножение производится независимо по двум «каналам», связанным с первым и вторым состояниями покоя машины . Наряду с операцией умножения двух или нескольких машин введем также операцию итерации, применяемую к одной машине. Пусть машина имеет s состояний покоя. Выберем какое-либо состояние покоя и отождествим его в основной таблице машины с начальным состоянием. Полученная машина, обозначаемая через

и является результатом итерации машины Т. Здесь точки указывают на отождествление состояния покоя с начальным состоянием машины . Если имеет лишь одно состояние покоя, то после применения итерации получается машина, не имеющая состояний покоя вовсе.

В дальнейшем будут использованы следующие обозначения. Если итерация производится над машиной, которая сама является результатом умножения и итераций других машин, то соответствующее число точек ставится над теми машинами, чьи состояния (покоя и начальные) отождествляются. Например, запись

означает, что состояние покоя машины отождествляется с начальным состоянием машины а состояние покоя — с начальным состоянием .

Приведем пример построения машины с помощью операций умножения и итерации. Пусть С, G, L и М — машины, описанные в предыдущем параграфе. Тогда машина

имеет в качестве основной таблицы табл. 13.29, построенную по описанным выше правилам из табл. 13.12, 13.20, 13.23 и 13.25. Машина N, находясь в начальный момент времени в состоянии напротив заполненной единицы слева от начального положения до того места, где впервые встречаются две пустые ячейки подряд, этого головка машины возвращается и останавливается у крайней правой заполненной ячейки той группы расположенных подряд единиц, из которой машина начинала работать.

В табл. 13.30 показан один вариант работы машины N. Приведены лишь те ситуации на ленте, при которых машина переходит из одного состояния в другое.

Таблица 13.29

Машина N

Таблица 13.30. (см. оригинал)

Для сокращения вместо символов состояний в таблице записаны их номера .

Таким образом, применение итерации позволяет составлять машины, повторяющие определенную последовательность операций на ленте (в приведенном примере машина N повторяет операцию «стирания» групп единиц до тех пор, пока левее некоторой группы единиц не окажутся две пустые ячейки).