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

UptoLike

ВУЗ: 

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

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

Рубрика: 

Математическая Логика и Теория Алгоритмов стр. 53 из 64
© 2003 Галуев Геннадий Анатольевич
цию |
2
q . После команды
22
| lqq в рабочей ячейке будет пробел В предшествующий
коду
y
. Тогда по команде
32
Blqq приходим к ситуации |
3
q . Команда
33
| Bqq сотрет
первую черточку кода
y
. В итоге мы построим следующую таблицу Тьюринга:
1.
10
Blqq 3.
21
Blqq 5.
32
Blqq
2.
21
| Bqq 4.
22
| lqq 6.
33
| Bqq ,
которая задает МТ выполняющую сложение чисел в унитарном коде.
Лекция 10.
Диаграммы Тьюринга.
Рассматривая выше пример синтеза числовой МТ, мы получили таблицу Тью-
ринга, включающую 6 команд, описывающих простейшие операции по просмотру
массива унитарного кода и стиранию двух его элементов. При выполнении более
сложных операций число команд таблицы существенно возрастает, что усложняет
процесс синтеза МТ. Для облегчения синтеза МТ используют композицию элементар-
ных МТ. Набор
элементарных МТ как правило ограничен и все они имеют фиксиро-
ванную систему команд. Если каким-нибудь образом обозначить элементарные МТ и
указать связи между ними, то результат их композиции будет представлять собой
диаграмму Тьюринга (ДТ).
Пусть
},...,,{
10 n
xxxX = - входной алфавит, r, l – сдвиг ленты соответственно вправо и
влево, S –стоп,
0
x или В пробел,
*
x
- множество слов над Х, А – слово в алфавите Х.
Будем считать, что двухбуквенный алфавит Х состоит из В и | (черточка). Бу-
дем обозначать через ~ произвольную последовательность букв, несущественную в
данном контексте, а через ~ - несущественную в данном контексте букву. Пусть ↑
указывает букву, которую в данном шаге просматривает считывающая головка
МТ.
С учетом сказанного можно привести несколько примеров элементарных МТ:
а) МТ
i
x . Примененная к произвольной позиции, печатает в рабочей ячейке букву
i
x .
Очевидно, что таблица Тьюринга для этой машины имеет вид:
100
qxxq
i
. . . . . . . .
. . . . . . . .
10
qxxq
in
б) МТ r. Примененная к произвольной позиции, сдвигает ленту на одну ячейку вправо
и останавливается.
в) МТ l. Аналогичная МТ со сдвигом влево.
Для МТr и МТl имеем таблицу Тьюринга:
100
rqxq
100
lqxq
. . . . . . . . . . . . . .
10
rqxq
n
10
lqxq
n
г) МТ, выполняющая трехкратный сдвиг ленты вправо и печать на ней буквы
0
x
100
rqxq
302
rqxq
. . . . . . . . . . . . . . . .

Страницы