Машина Тьюринга и рекурсивные функции. Кацаран Т.К - 9 стр.

qi на новое q j , в котором будет машина в момент времени t +1 (может

быть, что qi � q j ).

      Такие действия устройства управления называют командой, которую
можно записать в виде:
                                  qi ai � a j D q j ,                          (1)
где qi – внутреннее состояние машины в данный момент; a i – считываемый в
этот момент символ; a j – символ, на который изменяется символ a i (может быть

ai � a j ); символ   D   есть или Н, или Л, или П и указывает направление движения

головки; q j – внутреннее состояние машины в следующий момент (может быть

qi � q j ). Выражения qi ai и a j D q j называются левой и правой частями этой

команды соответственно. Число команд, в которых левые части попарно различ-
ны, является конечным числом, так как множества Q \ {q 0 } и A конечны.
      Не существует команд с одинаковыми левыми частями, т. е. если про-
грамма машины T содержит выражения qi ai � a j D q j и qt at � ak D qk ,

то qi � qt или ai � at и D � {П , Л , Н } .
      Совокупность всех команд называется программой машины Тьюринга.
      Максимальное число команд в программе равно (n � 1) � m , где

n � 1 � A и m � 1 � Q . Считается, что заключительное состояние команды

q0 может стоять только в правой части команды, начальное состояние q1
может стоять как в левой так и в правой части команды.
      Выполнение одной команды называется шагом. Вычисление (или ра-
бота) машины Тьюринга является последовательностью шагов одного за
другим без пропусков, начиная с первого.
      Итак, МТ задана, если известны четыре конечных множества: внешний
алфавит A , внутренний алфавит Q , множество D перемещений головки и
программа машины, представляющая собой конечное множество команд.

                                            9