Суперпозиция машин Тьюринга
Относительно МТ применимы такие соглашения:
работа машины однозначно определена функционированием УУ в соответствии с её функциональной схемой;
МТ всегда начинает работу от начального состояния (символ q1) и имеет состояние покоя (символ q0), которым заканчивается её работа.
Эти соглашения позволяют определить операции над МТ, благодаря которым можно по заданным ФС получать новые ФС. Различают следующие операции над машинами Тьюринга: композиция (произведение) и ите-рация, а также их комбинации, что позволяет строить суперпозиции МТ.
Пусть имеются две МТ: Т1 и Т2. Произведением МТ Т1 и Т2 называется машина Т, T=T1T2, ФС которой строится так:
если
УУ машин Т1 и Т2 имеют m1
и m2
состояний соответственно (исключая
состояние покоя), то УУ машины Т имеет
m1+m2
состояний, причём начальным состоянием
машины Т является начальное состояние
машины Т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 = ТТ...Т - n раз.
До сих пор рассматривалось умножение машин, имеющих одно состояние покоя. В том случае, когда одна из перемножаемых машин имеет несколько состояний покоя, умножение определяется аналогично описанному, но обязательно должно присутствовать указание, какое из состояний покоя предыдущего сомножителя отождествляется с начальным состоянием данного. Так, например, если машина Т1 имеет два состояния покоя, то произведение Т1 и Т2 может быть обозначено через
T=T1
либо T=T1
(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 pq, и соответственно проводим переобозначение состояний в двух других колонках с учётом правил передачи эстафеты управления. В результате получаем табл. 2.8.
Таблица 2.8
|
C D B A |
N |
0 |
1 |
Список обозначений
|
|
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).
3
.
В соответствии с табл. 2.8 строим граф
переходов машиныN (рис. 2.5,в),
отмечая на переходах из состояния в
состояние реакцию УУ (команды головке
на запись символа в ячейке и на перемещение
головки) в зависимости от символа,
обозреваемого головкой на ленте.
На рис. 2.6 приведен пошаговый процесс обработки данных на ленте (подчёркнута ячейка, над которой находится головка в данном такте; жирным шрифтом отмечена цифра, которая изменилась на прошлом такте).
Такт Номер Ситуация на ленте
состояния
0 1 …110100111100…
1 1 …110100111100…
2 1 …110100111100…
3 1 …110100111100…
4 1 …110100111100…
5 2 …110100111100…
6 3 …110100111100…
7 3 …110100111100…
8 1 …110000111100…
9 2 …110000111100…
10 4 …110000111100…
11 4 …110000111100…
12 0 …111000111100…
Рис. 2.6. Ситуации на ленте (к концу такта) при работе машины N
4. По СА функционирования (это можно сделать и по ФС) сформируем один из вариантов словесного описания алгоритмов функционирования машины N: машина, двигаясь влево, проходит группы пустых или заполненных ячеек, причём первую заполненную ячейку после группы пустых очищает, отыскивает на ленте одинокую пустую ячейку (ситуацию ...101...), заполняет её и останавливается над ней.
Отметим, что при отсутствии на ленте указанной ситуации головка дойдёт до левой границы ленты, что можно рассматривать как аварийное завершение работы машины.