9.3. Способы композиции машин Тьюринга

1. Последовательное подключение одной машины Тьюринга к другой. Пусть и – две машины Тьюринга над алфавитом {0,1}, множества состояний машин не пересекаются. Перенумеруем 0,1,…,L-1 все команды с программы . Пусть P(X) – предикат на множестве {0,1,…,L-1}. Последовательное подключение К (относительно предиката P(X)) – это машина Тьюринга , которая получается следующим образом. Первая половина таблицы для совпадает с таблицей для тех клеток, в которых нет команды с .

Если P(N)=1, то в клетке N – команда , – номер строки (0 или 1), где находится клетка N, – начальное состояние .

Если P(N)=0, то в клетке N – команда с . Вторая половина таблицы Т полностью совпадает с таблицей .

	……	……
0
1

В частном случае, если – начальное состояние машины , а – начальное состояние , заменим в программе состояние на состояние , и полученную программу объединим с программой . В результате мы получим программу для машины , которая является композицией машин И по паре состояний (,).

2. Итерация машины Тьюринга. Пусть – машина Тьюринга над алфавитом {0,1}. Перенумеруем 0,1,…,L-1 все команды с программы . Пусть P(X) – предикат на множестве {0,1,…,L-1}. Итерация машины Тьюринга относительно предиката P(X) – это машина Тьюринга Т, которая получается следующим образом. Таблица Т совпадает с таблицей для тех клеток, в которых нет команды не с .

Если P(N)=1, то в клетке N – команда , A – номер строки, где находится клетка N, – начальное состояние .

Если P(N)=0, то в клетке N – команда с .

Действительно, имеет место итерация, т. е. многократная работа машины .

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

Отметим, что начальных и заключительных состояний может быть несколько.

< Предыдущая		Следующая >