Дискретная математика. Элементы теории, задачи и упражнения. Часть 2. Булгакова И.Н. - 70 стр.

   символа на ленте, над которым находится головка, выполняет следую-
   щие действия:
a) «считывает» символ a i — заменяет на новый символ a j (может быть
   a j � a i );
b) перемещает головку в одном из направлений: П , Л , Н ;
c) изменяет имеющееся в момент t внутреннее состояние ql на новое со-
   стояние q s , в котором будет машина в последующий момент времени
   t � 1 (может быть q l � q s ).
      Такие действия УУ называется командой, которая записывается так:
                                  ql a i � a j D q s ,             (1)
где a i , a j � A , ql , q s � Q , D � �П , Л , Н �, l � 0 .
       В левой части команды (*) никогда не встречается q0 .
       Так как множества A и Q конечны, то команд вида (1), в которых
левые части попарно различны, конечное число.
       Совокупность всех команд называется программой МТ. Макси-
мальное число команд в программе равно �n � 1� � m , где n � A , m � Q .
Считается, что заключительное состояние q0 может стоять только в правой
части команды, начальное состояние q1 — только в левой части команды.
       Если левые части двух команд совпадают, то с необходимостью сов-
падают и правые части команд. Выполнение одной команды называют ша-
гом. Ясно, что работа МТ полностью определяется ее программой.
       Заданное слово на ленте с начальным состоянием q1 и положение
головки над первым символом называется начальной конфигурацией. Го-
ворят, что МТ применима к слову начальной конфигурации, если при ра-
боте над этим словом через конечное число шагов выполняется команда,
содержащая в правой части заключительное состояние q 0 , и работа над
этим словом прекращается. То, что получилось при этом на ленте, вместе с
состоянием q0 и положением головки называют заключительной конфи-
гурацией. В противном случае говорят, что МТ не применима к слову на-
чальной конфигурации.
       Пример 1. Построить машину Тьюринга, которая в алфавите
 A � �a , b , �� слово " abb" преобразует в слово " bba" .
       Решение. Составим программу МТ:
                                    q1 a � � П q2
                                       q2 b � b П q2
                                       q 2 � � a Н q0



                                           70