Теория алгоритмов, формальных языков, грамматик и автоматов. Бильгаева Н.Ц. - 15 стр.

    q01 → q00R,        q10 → q10L,
    q00 → q01R,        q11 → q11L,
    q0 ε → q1εL,       q1ε → qzεR.
       В стандартной начальной конфигурации головка стоит над первым символом слева, и
устройство управления находится в начальном состоянии. На следующем такте машина
Тьюринга, не меняя своего состояния, заменяет символ 0 на 1 или 1 на 0 и сдвигается вправо
на один символ. После просмотра всей цепочки под головкой оказывается символ,
указывающий на пустую ячейку. В этом случае машина Тьюринга переходит в новое
состояние и сдвигается влево на один символ. На последующих тактах управляющее
устройство не меняет своего состояния, оставляет без изменения символ под головкой и
перемещается влево до тех пор, пока не встретит пустую ячейку. Встретив пустую ячейку,
машина Тьюринга переходит в заключительное состояние и перемещается вправо на один
символ, переходя в стандартную заключительную конфигурацию.

      3.4.2. Представление машины Тьюринга графом
    При представлении машины Тьюринга посредством графа необходимо каждому
состоянию поставить в соответствие вершину графа, а каждой команде - помеченную дугу.
    Машина Тьюринга из рассмотренного примера инвертирования цепочки, состоящей из
символов 0 и 1, будет представлена в виде графа следующим образом:
                                0→1R           0→0L

                                       ε→εL               ε →R
                                q0                   q1             qz

                                1→0R           1→1L

    Начальная и конечная вершины графа обычно выделяются; на рисунке они отмечены
черным кружком. Если на очередном такте работы машины Тьюринга символ на ленте не
изменяется, то в правой части команды его можно не писать (ε на ребре в состояние qz ).

          3.4.3. Представление машины Тьюринга таблицей соответствия
     При представлении машины Тьюринга данным способом составляется таблица, в
которой каждому состоянию соответствует строка, а каждому символу из входного алфавита
- столбец. В клетках таблицы на пересечении строки и столбца будет находиться действие
(или правая часть команды).
     Таблица соответствия для задания машины Тьюринга из рассмотренного примера будет
выглядеть следующим образом:
                                     0       1             ε
                           q0        q0 1R   Q0 0R         q1 ε L
                           q1        q1 0L   Q1 1L         q z εL
   Инвертирование входной цепочки можно выполнить программой машины Тьюринга,
приведенной в таблице соответствия. Эта программа включает шесть команд.

      3.5. Вычислимые функции
    Говорят, что машина Тьюринга вычисляет функцию f(x1, x2, ..., xn), если выполняются
следующие условия: