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

      Работа машины Тьюринга состоит в последовательном применении
команд, причем, применение той или команды определяется текущей кон-
фигурацией. Так в приведенном выше примере должна применится коман-
да с левой частью q1a1 .
      Итак, зная программу и задав начальную конфигурацию, полностью
определяем работу машины над словом в начальной конфигурации.
      Если в работе машины Тьюринга в некоторый момент t выполняется
команда, правая часть которой содержит q0 , то в такой момент работа маши-
ны считается законченной, и говорят, что машина применима к слову на лен-
те в начальной конфигурации. В самом деле, q0 не встречается в левой части
ни одной команды – этим и объясняется название q0 «заключительное со-
стояние». Результатом работы машины в таком случае считается слово, кото-
рое будет записано на ленте в заключительной конфигурации, т. е. в конфи-
гурации, в которой внутреннее состояние машины есть q0 . Если же в работе
машины ни в один из моментов не реализуется команда с заключительным
состоянием, то процесс вычисления будет бесконечным. В этом случае гово-
рят, что машина не применима к слову на ленте в начальной конфигурации.

    § 3. Примеры машин Тьюринга, работающих в алфавите {a, b}

      Проиллюстрируем работу машину Тьюринга на следующем примере.

      Пример 1. Построить машину Тьюринга T1 , которая применима ко
всем словам с внешним алфавитом {a, b} и делает следующее: любое слово
x1 x2 ...xn , где xi � a или xi � b (i � 1,2,...n) преобразует в слово x2 ...xn x1 ,
т. е., начиная работать при слове x1 x2 ...xn на ленте в начальной конфигу-
рации, машина остановится, и в заключительной конфигурации на некото-
ром участке ленты будет записано слово x2 ...xn x1 , а все остальные клетки
ленты (если такие будут) окажутся пустыми.
                                        11