Параллельная композиция машин Тьюринга
Параллельной композицией машин Параллельная композиция МТ
и обозначается: Фактически параллельная композиция двух МТ получает на вход слово, состоящее из 2-х слов в разных алфавитах, и на выходе выдает слово, также состоящее из 2-х слов, т.е. представляет собой две одновременно и независимо работающие машины. Для реализации параллельной композиции используется машина с двухэтажной лентой. Машина с двухэтажной лентой работает следующим образом: 1) слово 2) вычисляется 3) вычисляется 4) Команда МТ с двухэтажной лентой записывается следующим образом:
где Продемонстрируем работу машины Тьюринга с двухэтажной лентой. В общем случае длины слов
Для реализации параллельной композиции n машин Тьюринга используется n– этажная лента.
|
и 
, вычисляющих словарные функции 
и 
в алфавитах А и В, соответственно, называется машина M, вычисляющая словарную функцию 
. Здесь знак 
используется для разделения слов при параллельной композиции МТ.
.
переписывается на второй этаж ленты и стирается на первом,
на первом этаже,
,
– буквы, записанные соответственно на первом и втором этажах. Обозначим длины слов 
, соответственно, 
.
не совпадают между собой, но для простоты изображения принимаем, что они равны. Тогда реализация пунктов 1)-4) на МТ с двухэтажной лентой выполняется таким образом:
