Математическая логика и теория алгоритмов. Галуев Г.А. - 50 стр.

UptoLike

ВУЗ: 

ТТИ ЮФУ | Таганрог

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

Рубрика: 

Математическая Логика и Теория Алгоритмов стр. 50 из 64
© 2003 Галуев Геннадий Анатольевич
сдвинута вправо или влево. Конкретные действия определяются ситуацией, в которой
находится машина, и командами перехода.
Пусть
n
xxx ,...,,
10
- символы входного алфавита Х, буквы которого могут быть за-
писаны на ленте.
Символ
0
x отождествляется с нулевым символом. Иногда этот символ обозначается
как В и называется пробелом. Считается, что все незанятые ячейки ленты заняты
пробелами.
Пусть
},...,,{
10 m
qqqQ = - алфавит внутренних состояний устройства управления
МТ. Состояние
0
q - начальное состояние. Предполагается, что в исходном состоянии
МТ находится в состоянии
0
q , а считывающая головка обозревает крайний левый
символ входной цепочки.
Пусть
},,{ srlI = - множество инструкций управления движением ленты. Символ
l -означает сдвиг ленты на одну ячейку влево (
←
);
r
- сдвиг вправо, s - отсутствие
движения или остановка ленты. Заметим, что
l и
r
можно употреблять в противопо-
ложном значении, если полагать, что лента неподвижна, а движется головка считы-
вания.
МТ условно можно изобразить следующим образом
Ситуацией называется пара
XxQqxq
jiji
∈∈ ,; . Очевидно, начальная ситуация
МТ (указанной на рисунке) есть
α
xq
0
. Выражением будем называть конечную после-
довательность символов в алфавите
},,,,...,,,,...,,{
1010
srlqqqxxx
mn
.
Командой называется выражение одного из следующих типов
jlki
qxxq ;
jki
rqxq ;
jki
pqxq
;
jki
sqxq
- команда остановки.
Конечная последовательность команд, задающая функционирование МТ, назы-
вается таблицей Тьюринга. Если в таблице все команды имеют попарно различные
ситуации, то соответствующая ей МТ называется детерминированной.
Кроме того, функционирование МТ можно задавать с помощью так называемых
таблиц Айзермана, определяющих отображения
QвXQ ×:
δ
, XвXQ ×:
μ
и
IвXQ×:
λ
и называемых соответственно таблицами преобразования сигнала, за-
писи ленты и таблицей преобразования перемещения ленты. Эти три таблицы можно
объединить в одну обобщенную таблицу.
Конфигурацией называется выражение вида
lkji
xxxq ... , в котором
i
q не может
занимать крайней правой позиции.
В
α
x
β
x
γ
x
δ
x
λ
x
В
Управляющее
устройство
Голо
в
ка
Рабочая ячейка
rl ←→
Ле
н
r
l
←→
- если движется головка

Страницы