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

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

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




     Задачи.

       1. По заданной машине Тьюринга T и начальной конфигурации K1 найти
заключительную конфигурацию:
          ⎧q1 0q11R
1) T : ⎨               ; K1 = 1q1 013 .
          ⎩q11q01E
        ⎧q1 0q11R
        ⎪q 1q 1L
        ⎪ 1 2
2) T : ⎨                 ; K1 = q11013 .
        ⎪q 2 0 q 0 0 R
        ⎪⎩q 2 1q1 0 R
       ⎧q1 0q21R
       ⎪q 1q 0 L
       ⎪ 1 2
3) T : ⎨                ; K1 = 10 21q11 .
       ⎪q2 0q01E
       ⎪⎩q21q11L
         ⎧q1 0q 2 0 R
         ⎪q 1q 1L
         ⎪ 1 2
4) T : ⎨                 ; K1 = 1012 q112 .
         ⎪q 2 0 q 0 0 E
         ⎪⎩q 2 1q11R



                                       58