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

     Операции с машинами Тьюринга.

     Очевидно, что некоторые алгоритмы могут быть составлены из нескольких
более простых алгоритмов, и наоборот, могут служить основой для построения
новых алгоритмов.
     Точно также, удобно строить машины Тьюринга, исходя из уже построенных
машин.

     Принцип двойственности.

     Пусть Т – произвольная программа (машина Тьюринга). Обозначим Т*
программу, которая получается из Т заменой (во всех командах) R на L и наоборот.
Программа Т* называется двойственной к Т.

      Пример. Машина Тьюринга в произвольной записи, начиная с любой ячейки,
двигаясь вправо, находит первый нуль. Соответствующая программа имеет вид:
         ⎧q1 0q0 0 E
      T :⎨           .
         ⎩q11q11R
      Возможны три случая.
      1. В начальный момент головка машины обозревает нуль. Машина
останавливается.
      2. В начальный момент головка машины обозревает единицу, и справа от
начальной ячейки есть хотя бы один нуль. Машина переместит головку через массив
единиц вправо и остановится перед первым нулем.
      3. В начальный момент головка машины обозревает единицу, и справа от
начальной ячейки запись состоит только из единиц. Машина будет перемещать
головку через массив единиц вправо, не останавливаясь.
      В программе заменим символ R на L. Получим программу:
         ⎧q1 0q0 0 E
      T :⎨           .
         ⎩q11q11L
      Данная программа будет двойственной к предыдушей. Непосредственной
проверкой можно убедиться, что головка машины, двигаясь влево, будет отыскивать
первый нуль.

     Очевидно, что (Т*)*=Т, то есть понятие двойственности является взаимным.
Машины Тьюринга, соответствующие двойственным программам, будем называть
двойственными машинами Тьюринга.
     Из примера было видно, что двойственные машины функционируют
симметричным образом. Так, пусть в начальный момент времени имеется
конфигурация



                                       56