Дискретная математика. Элементы теории, задачи и упражнения. Часть 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