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

UptoLike

Операция замыкания . Основные замкнутые классы .
__________________________________________________________________________________________
126
1
q
(начальная конфигурация)
Λ
b
b
Λ
2-й шаг
2
q
Λ
b
b
Λ
3-й шаг
2
q
Λ
b
b
Λ
4-й шаг
2
q
Λ
b
b
a
5-й шаг
0
q
(заключительная конфигу -
рация)
Работа МТ закончена.
Работу МТ можно описать следующим образом : она запоминает 1-ю
букву исходного слова (или при этом стирает его ); головка движется впра -
во до первой пустой клетки, в которую и записывается первая буква ис-
ходного слова .
Замечание. Часто программу МТ записывают в другой, более ком-
пактной форме в виде таблицы. Например, программа примера 1 может
выглядеть следующим образом:
Λ
a
b
1
q
2
qП
Λ
2
q
0
qНa
2
qПb
Пример 2. Построить машину Тьюринга , вычисляющую числовую
функцию
(
)
.Nx,xxS
1
Решение. Пусть внешним алфавитом данной МТ является множест -
во
{
}
1,A
Λ
. Число
N
x
на ленте машины записывать в виде набора из
x
единиц: