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

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

                        ↓
                Λ       a       b      b       Λ            — 1-й шаг