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

шаге машина останется в прежнем состоянии q 2 , сохранит содержимое
обозреваемой ячейки b и перейдет к обозрению следующей левой ячейки
на ленте.
     Предположим, что в начальной конфигурации головка находится над
крайней правой клеткой.
     Применим эту машину к слову bbcbb. Последовательность конфигура-
ций, возникающих в процессе работы машины (исходная конфигурация –
стандартная начальная):
   bbcbq1b � bbcq2 ba � bbq 2 cba � bq 2 bcba � q 2 bbcba � q 2 abbcba �

� bq3bbcba � bbq3bcba � bbbq3 cba � bbbcq3ba � bbbcbq3 a � bbbcq1ba �

� bbbq 2 caa � bbq 2 bca � bq 2 bbca � q 2 bbbca � q 2 abbbca � bq3bbbca �

� bbq3bbca � bbbq3bca � bbbbq3 ca � bbbbcq3 � bbbbq1ca � bbbbq0 aa.

     Нетрудно заметить, что данная МТ реализует операцию сложения: в
результате ее работы на ленте записано подряд столько букв b , сколько их
было всего записано по обе стороны от буквы c перед началом работы
машины.
     Из приведенных примеров следует, что МТ – это некоторое правило
(алгоритм) для преобразования слов алфавита A � Q , т. е. конфигураций.
Таким образом, для определения (построения) машины Тьюринга нужно
задать ее внешний и внутренний алфавиты, программу и указать, какие из
символов обозначают пустую ячейку и заключительное состояние.

            § 4. Способы задания машин Тьюринга, операции над ними

     Рассмотрим три основные операции, применяемые над машинами
Тьюринга.
     1. Пусть машины Тьюринга Т1 и Т2 имеют соответственно про-
граммы П1 и П2. q10 – заключительное состояние Т1, q12 – начальное со-
                                    15