Математическая логика и теория алгоритмов. Сергиевская И.М. - 52 стр.

...qi a1a 2 ... ,
и машина Т в момент времени t переработает ее в конфигурацию
...c1c2 ...qi c s ... .
В то же время, двойственная машина Т* конфигурацию
 ...a2 qi a1 ...
(симметричную первой конфигурации относительно a1 ) в момент времени t
переработает в конфигурацию
          ...qi c s ...c2 c1... ,
симметричную второй конфигурации относительно c1 .

В Содержание.



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

     1.     Последовательное подключение одной машины Тьюринга к другой.
Пусть T0 и T1 – две машины Тьюринга над алфавитом {0,1}, множества состояний
машин не пересекаются. Перенумеруем 0,1,…,l-1 все команды с q0 программы T0 .
Пусть p(x) – предикат на множестве {0,1,…,l-1}. Последовательное подключение
T1 к T0 (относительно предиката p(x)) – это машина Тьюринга T , которая
получается следующим образом. Первая половина таблицы для T совпадает с
таблицей T0 для тех клеток, в которых нет команды с q0 .
     Если p(n)=1, то в клетке n – команда q1 ' aE , a – номер строки (0 или 1), где
находится клетка n, q1 ' – начальное состояние T1 .
      Если p(n)=0, то в клетке n – команда с q0 . Вторая половина таблицы Т
полностью совпадает с таблицей T1 .

             q1 … q j … qm          q1 ' … q j ' … qm '
     0
     1

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

     2.   Итерация машины Тьюринга. Пусть T0 – машина Тьюринга над
алфавитом {0,1}. Перенумеруем 0,1,…,l-1 все команды с q0 программы T0 . Пусть



                                          57