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

       Очевидно, что наилучший способ выполнить это требование состоит в
следующем. После начала работы считывающая головка машины должна пе-
реместиться на одну ячейку влево, записать в пустую ячейку 1 и остановиться.
       Первая команда имеет вид: q11 � 1Пq1 (см. рис. 2).
       Согласно этой команде, машина, находясь в состоянии q1 , читает сим-
вол 1, записанный в обозреваемой ячейке, оставляет этот символ в ячейке,
остается в прежнем состоянии q1 и сдвигается на одну ячейку ленты вправо.
       Вторая команда имеет вид: q1 � � 1Hq 0 (см. рис. 3).
       Таким образом, согласно этой команде, машина, находясь в состоя-
нии q1 , читает пустой символ, записанный в обозреваемой ячейке, записы-
вает на его место символ 1, переходит в состояние q0 и останавливается.
       Программа работы машины Тьюринга также может быть записана в
виде таблицы. Столбцам таблицы соответствуют символы внешнего алфа-
вита, а строкам – состояние машины.
       В рассматриваемом примере таблицы работы машины Тьюринга
имеет вид:


                                        �            1
                                q1    1 Н q0       1П q1


       Пример 6. Построить машину T4 , вычисляющую числовую функ-
цию f ( x, y ) � x � y.
       Решение. Пусть внешним алфавитом данной машины является алфа-
вит {�,1} . Работа машины состоит из конфигураций:
                 q11 � 1Пq1 , q1 � � 1Пq 2 , q 2 1 � 1Пq 2 , q 2 � � �Лq 3 ,
                               q 3 1 � �Лq 4 , q 4 1 � �Лq 0 .
       Следует отметить, что для данной машины T4 выписаны все коман-
ды, осуществляющие вычисление функции f ( x, y ) � x � y.
                                          22