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

UptoLike

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

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