Параллельная композиция машин Тьюринга

Параллельной композицией машин и , вычисляющих словарные функции и в алфавитах А и В, соответственно, называется машина M, вычисляющая словарную функцию . Здесь знак используется для разделения слов при параллельной композиции МТ.

Параллельная композиция МТ и изображается следующим образом:

и обозначается: .

Фактически параллельная композиция двух МТ получает на вход слово, состоящее из 2-х слов в разных алфавитах, и на выходе выдает слово, также состоящее из 2-х слов, т.е. представляет собой две одновременно и независимо работающие машины. Для реализации параллельной композиции используется машина с двухэтажной лентой.

Машина с двухэтажной лентой работает следующим образом:

1) слово переписывается на второй этаж ленты и стирается на первом,

2) вычисляется на первом этаже,

3) вычисляется на втором этаже

4) переписывается на первый этаж, возможно, со сдвигом.

Команда МТ с двухэтажной лентой записывается следующим образом:

,

где – буквы, записанные соответственно на первом и втором этажах. Обозначим длины слов , соответственно, .

Продемонстрируем работу машины Тьюринга с двухэтажной лентой. В общем случае длины слов и не совпадают между собой, но для простоты изображения принимаем, что они равны. Тогда реализация пунктов 1)-4) на МТ с двухэтажной лентой выполняется таким образом:

								…

Для реализации параллельной композиции n машин Тьюринга используется n– этажная лента.