Дискретная математика. Элементы теории, задачи и упражнения. Часть 2. Булгакова И.Н. - 71 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

Составители: 

Рубрика: 

71
В результате работы МТ над словом
"
abb
"
будут следующие шаги:
¯
L
a
b
b
L
– 1-й шаг
1
q
(начальная конфигурация)
¯
L
b
b
L
– 2-й шаг
2
q
¯
L
b
b
L
– 3-й шаг
2
q
¯
L
b
b
L
– 4-й шаг
2
q
¯
L
b
b
a
– 5-й шаг
0
q
(заключительная конфигу-
рация)
Работа МТ закончена.
Работу МТ можно описать следующим образом: она запоминает 1-ю
букву исходного слова (или при этом стирает его); головка движется впра-
во до первой пустой клетки, в которую и записывается первая буква ис-
ходного слова.
Замечание. Часто программу МТ записывают в другой, более ком-
пактной форме в виде таблицы. Например, программа примера 1 может
выглядеть следующим образом:
L
a
b
1
q
2
qП
L
2
q
0
qНa
2
qПb
Пример 2. Построить машину Тьюринга, вычисляющую числовую
функцию
)
.Nx,xxS
Î
+
=
1 
В результате работы МТ над словом " abb" будут следующие шаги:


                  �
            �     a     b    b     �         – 1-й шаг
                  q1                         (начальная конфигурация)

                       �
                  �    b     b     �         – 2-й шаг
                       q2

                             �
                  �     b    b     �         – 3-й шаг
                             q2

                                  �
                  �     b    b    �          – 4-й шаг
                                  q2

                                   �
                  �     b    b     a         – 5-й шаг
                                   q0        (заключительная конфигу-
                                             рация)
     Работа МТ закончена.

     Работу МТ можно описать следующим образом: она запоминает 1-ю
букву исходного слова (или при этом стирает его); головка движется впра-
во до первой пустой клетки, в которую и записывается первая буква ис-
ходного слова.

     Замечание. Часто программу МТ записывают в другой, более ком-
пактной форме в виде таблицы. Например, программа примера 1 может
выглядеть следующим образом:
                           �       a        b
                   q1            � П q2
                   q2    a Н q0           b П q2


     Пример 2. Построить машину Тьюринга, вычисляющую числовую
функцию
                          S � x � � x � 1, x � N .
                                   71

Страницы