Суперпозиция машин Тьюринга

Относительно МТ применимы такие соглашения:

· работа машины однозначно определена функционированием УУ в соответствии с её функциональной схемой;

· МТ всегда начинает работу от начального состояния (символ q₁) и имеет состояние покоя (символ q₀), которым заканчивается её работа.

Эти соглашения позволяют определить операции над МТ, благодаря которым можно по заданным ФС получать новые ФС. Различают следующие операции над машинами Тьюринга: композиция (произведение) и ите-рация, а также их комбинации, что позволяет строить суперпозиции МТ.

Пусть имеются две МТ: Т1 и Т2. Произведением МТ Т1 и Т2 называется машина Т, T=T₁T₂, ФС которой строится так:

· если УУ машин Т1 и Т2 имеют m₁ и m₂ состояний соответственно (исключая состояние покоя), то УУ машины Т имеет m₁+m₂ состояний, причём начальным состоянием машины Т является начальное состояние машины Т1 (), а конечным - состояние покоя машины Т2 (), т. е. машина Т1 начинает работу, затем передает «эстафету управления» машине Т2, а Т2 заканчивает её;

· ФС машины Т состоит из двух частей: верхняя описывает машину Т1, а нижняя - Т2, причём состояние покоя Т1 отождествляется с начальным состоянием Т2, т. е.

Операция умножения машин обладает свойствами:

1) Т1 Т2 ¹Т2 Т1 (некоммутативность);

2) ( Т1 Т2 ) Т3 = Т1 ( Т2 Т3 ) = Т1 Т2 Т3 (ассоциативность).

Возможен случай произведения одинаковых машин - степень МТ:

Тⁿ = ТТ...Т - n раз.

До сих пор рассматривалось умножение машин, имеющих одно состояние покоя. В том случае, когда одна из перемножаемых машин имеет несколько состояний покоя, умножение определяется аналогично описанному, но обязательно должно присутствовать указание, какое из состояний покоя предыдущего сомножителя отождествляется с начальным состоянием данного. Так, например, если машина Т1 имеет два состояния покоя, то произведение Т1 и Т2 может быть обозначено через

T=T₁либо T=T₁ (2.13)

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

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

Т=T1. (2.14)

Здесь умножение производится независимо по двум "каналам", которые связаны с первым либо вторым состоянием покоя машины Т1.

Рассмотрим операцию итерации, которая применяется к одной машине. Пусть машина Т1 имеет r состояний покоя. Выберем какое-либо l-е состояние покоя и отождествим его в ФС машины Т1 с начальным состоянием. Полученная машина является результатом итерации машины Т1 и обозначается через

Т= . (2.15)

Здесь точки над Т1 и l указывают на отождествление l-го состояния покоя машины Т1 с её начальным состоянием ( ). Отметим, что если Т1 имеет лишь одно состояние покоя, то после применения итерации получается машина, не имеющая вовсе состояния покоя.

Если обратиться к понятию ²программа² для МТ, то, как не трудно видеть, композиции машин соответствует линейное представление общей программы, итерации - циклическое представление, а множеству стоп-состояний – разветвление в программе. Таким образом, в программе (алгоритме, поскольку программа – одно из представлений алгоритма) для суперпозиции МТ можно выделить три базовых фрагмента, присущих схемам алгоритма. Из этого следует принципиальная возможность создания МТ (её ФС), реализующей любой алгоритм. Эта возможность утверждается в основной гипотезе теории алгоритмов: всякий алгоритм может быть задан посредством тьюринговой функциональной схемы и реализован в соответствующей машине Тьюринга.

Пример 2.7 Пусть имеются 4 машины (A, B, C и D), заданные своими ФС (табл. 2.4 - 2.7). Суперпозиция N из заданных МТ описывается формулой

(2.16)

Для суперпозиции N требуется построить: 1) функциональную схему; 2) схему алгоритма; 3) граф переходов, а также записать словесное описание работы машины N.

1. Составляем для машины N функциональную схему, заполняя её строками из ФС каждой исходной машины в том порядке, в каком они записаны в формуле (слева направо и сверху вниз); далее записываем состояния в первой колонке таблицы в порядке возрастания их номеров, обозначив состояния машины N pºq, и соответственно проводим переобозначение состояний в двух других колонках с учётом правил передачи ²эстафеты управления². В результате получаем табл. 2.8.

Таблица 2.8

C D B A	N			Список обозначений
p1	p20L	p11L
p2	p30S	p41S
p3	p30L	p10L
p4	p01S	p41R

2. По полученной ФС строим схему алгоритма, исходя из того, что каждая строка ФС может рассматриваться как условный оператор программы функционирования МТ, а состояние (имя строки) – как метки этой программы.

На рис. 2.5,а представлена СА функционирования машины N. Здесь SL(x) (SR(x)) – процедура SEARCH поиска на ленте символа x (X={0, 1}) при движении головки влево (вправо); R, L, S – команды на перемещение головки; Z - содержимое текущей ячейки. Для примера на рис. 2.5,б показана процедура SL(x).

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