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

UptoLike

Операция замыкания . Основные замкнутые классы .
__________________________________________________________________________________________
125
b) перемещает головку в одном из направлений:
Н
,
Л
,
П
;
c) изменяет имеющееся в момент
t
внутреннее состояние
l
q на новое со-
стояние
s
q
, в котором будет машина в последующий момент времени
1
+
t
(может быть
sl
qq
=
).
Такие действия УУ называется командой, которая записывается так:
sjil
qDaaq
, (*)
где
{
}
0
=
l,Н , Л , ПD,Qq,q,Aa,a
slji
.
В левой части команды (*) никогда не встречается
0
q
.
Так как множества
A
и
Q
конечны, то команд вида (*), в которых
левые части попарно различны, конечное число.
Совокупность всех команд называется программой МТ. Макси-
мальное число команд в программе равно
(
)
mn
+
1
, где .Qm,An ==
Считается, что заключительное состояние
0
q может стоять только в правой
части команды, начальное состояние
1
q только в левой части команды.
Если левые части двух команд совпадают, то с необходимостью сов-
падают и правые части команд. Выполнение одной команды называют ша-
гом . Ясно, что работа МТ полностью определяется ее программой.
Заданное слово на ленте с начальным состоянием
1
q и положение
головки над первым символом называется начальной конфигурацией. Го-
ворят , что МТ применима к слову начальной конфигурации, если при ра -
боте над этим словом через конечное число шагов выполняется команда,
содержащая в правой части заключительное состояние
0
q , и работа над
этим словом прекращается. То, что получилось при этом на ленте, вместе с
состоянием
0
q
и положением головки называют заключительной конфи-
гурацией. В противном случае говорят , что МТ не применима к слову на-
чальной конфигурации.
Пример 1. Построить машину Тьюринга , которая в алфавите
{
}
Λ
=
,b,aA
слово
"
abb
"
преобразует в слово
"
bba
"
.
Решение. Составим программу МТ:
02
22
21
q Н aq
q П bbq
qПaq
→Λ
Λ
В результате работы МТ над словом
"
abb
"
будут сле -
дующие шаги :
Λ
a
b
b
Λ
1-й шаг