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

UptoLike

ВУЗ: 

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

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

Рубрика: 

Математическая Логика и Теория Алгоритмов стр. 52 из 64
© 2003 Галуев Геннадий Анатольевич
1.
10112010
xxxxxxxq
2.
10112011
xxxxxxqx
3.
10112001
xxxxxqxx
4.
10110201
xxxxqxxx
5
10111201
xxxqxxxx
6.
10112201
xxxxqxxx
7.
10122201
xxxxqxxx
В последней (7) конфигурации у нас появляется (согласно инструкции
2212
qxxq ) ситуация
22
xq для которой у нас нет команды. Поэтому анализируемая МТ
на этом шаге останавливается (заменяет
1
x
на
2
x
и формирует ситуацию
22
xq
для ко-
торой нет команды).
Пусть теперь входное слово будет
221
xxx , тогда процесс вычисления примет
вид:
.....
0221
2021
2211
22
1
0
дтиBBqxxx
Bxqxx
xxqx
xxxq
т.к.
0
xB = , то согласно первой инструкции из примера 1 (т.е.
000
lqxq ) МТ будет рабо-
тать бесконечно и никогда не остановится (т.к. лента бесконечна).
Рассмотрим теперь сущность проблемы синтеза МТ и идею проведения синтеза
МТ на примере так называемых числовых МТ. В таких машинах алфавит состоит из
двух символов:
В-пробела и | (палочки, черточки). Произвольные целые числа представимые в
числовой МТ
кодируются унитарным кодом, следующим образом: |||,...2||,1|,0 === (чер-
та сверху означает кодированное число).
Построим простейшую МТ, вычисляющую сумму x+y любых двух целых неотри-
цательных чисел. На ленту занесем сначала первое число x, а затем через пробел В
второе число у. Вычисление начнем с крайней левой позиции, предположив, что МТ
находится в начальной ситуации
Bq
0
. Будем считать, что результат получен, если на
ленте осталось столько палочек, записанных не обязательно подряд, чему равно зна-
чение суммы. Это значение таково:
2
−
+
=
+
yxyx . Для построения МТ используем
следующую процедуру. Сначала выделим первую палочку кода
x
и стираем ее. Затем
выделяем первую палочку кода
y
и тоже стираем ее. В результате на ленте остает-
ся число палочек равное сумме х+у. При это заметим, что этот же результат можно
получить и другим способом(например, стирая не первые а последние палочки в ко-
дах
x
y
и так далее ). Исходя из этой идеи можно синтезировать множество ко-
манд, определяющих требуемую МТ. Действительно по команде
10
Blqq МТ перейдет из
начальной ситуации в рабочее состояние
1
q , а в рабочей ячейке появится первая па-
лочка кода
x
. Далее по команде
11
| Bqq эта палочка стирается и машина переходит с
ситуацию
Bq
1
. По команде
21
Blqq
машина МТ сдвинет ленту влево и перейдет в ситуа-

Страницы