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

  …         a0          a1       a2       …            an          …
                                                  ↑
                                                  q1
                                 Рис. 1

        Так, на рис. 1 считывающая головка обозревает ячейку ленты, в которой
  записан символ an . Управляющее устройство находится в состоянии q1
  (начальном состоянии). В зависимости от состояния управляющего устройства
  головка либо оставляет обозреваемый символ без изменения, либо записывает на
  его место любой другой символ внешнего алфавита, либо стирает обозреваемый
  символ. Далее головка либо остается на месте, либо передвигается на одну
  ячейку вправо или влево, при этом управляющее устройство переходит в
  некоторое новое состояние (состояние может и не меняться).

         Каждое перемещение головки и изменение состояния управляющего
устройства можно определить командой, которая обычно записывается в виде:
qi a j qij aij Dij .
Здесь:
• qi – состояние, в котором управляющее устройство находится в данный момент,
• a j - символ, обозреваемый головкой,
• qij – состояние, в которое управляющее устройство переходит в зависимости от
  состояния qi и обозреваемого символа a j ,
• aij – новый символ, который записывается в ячейку, и зависящий от qi и a j ,
• Dij – символ сдвига, указывающий направление движения головки (он также
   зависит от qi и a j ).
      Список команд для машины Тьюринга называется программой. Существует
взаимно однозначное соответствие между машинами Тьюринга и программами.
      Вид ленты в каждый момент времени может быть определен конфигурацией
вида:
      a j K a j qi a j K a j .
        1        l −1        l   s
      Головкой в данный момент обозревается символ                         a j , записанный в
                                                                            l
конфигурации первым справа от символа qi . Первый и последний символы в данной
конфигурации – непустые. Считается, что остальные символы на ленте, не
записанные в конфигурацию – пустые. Имеется в виду, что в данный момент
времени на ленте записано слово a j K a j a j K a j .
                                              1         l −1   l       s
     Конфигурация, соответствующая началу работы машины, называется
начальной. Если в процессе работы машина достигает заключительного состояния,
то соответствующая конфигурация называется заключительной. Машина может



                                                        53