Дискретная математика. Громов Ю.Ю - 69 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

69
До начала функционирования машины следует заполнить (если это
необходимо) некоторые клетки ленты символами, отличными от m
0
, пе-
ревести УГ в состояние s
0
и задать её исходное положение относительно
ленты. После этого машина будет функционировать в соответствии с
таблицей Т. Функционирование машины можно задать и с помощью графа,
вершины которого соответствуют состояниям этого устройства, дуги –
переходам из одного состояния в другое, при этом каждая дуга (s
j
, s
p
)
графа взвешена упорядоченной парой (m
i
, m
k
d
l
).
Описанное гипотетическое устройство называется по имени англий-
ского математика Алана Тьюринга (1912 − 1954) машиной Тьюринга.
Рассмотрим пример машины Тьюринга, предназначенной для сло-
жения двух чисел в унарной системе счисления.
Внешний алфавит этой машины представляет собой множество
M = {λ, 1, 0, *, =}, в котором элемент λ обозначает пустой символ; внут-
ренний алфавит − множество S = {s
0
, s
1
, s
2
, s
3
, s
4
, s
5
} состояний УГ и
алфавит перемещений − множество D = {П, Л, Н}. Пусть на ленте
(рис. 32) записаны два числа, представленные с помощью цифры ‘1’ и
разделённые символом ‘*’, а УГ находится в состоянии s
0
и видит первую
слева единицу.
Работа машины Тьюринга характеризуется функциональной табли-
цей Т (табл. 15).
В соответствии с этой таблицей УГ машины считывает числа с ленты,
записывает непосредственно после них символ ‘=’, а затем результат сло-
жения также в унарной системе счисления. На рисунке 33 представлены
конечное содержимое ленты, а также конечное положение и состояние УГ.
λ λ 1 1 1 * 1 1 λ λ
Таблица 15
s
0
s
1
s
2
s
3
s
4
s
5
λ (=, П, s
2
) (1, Л, s
3
) (λ, П, s
5
)
1 (0, П, s
1
) (1, П, s
1
) (1, П, s
2
) (1, Л, s
3
) (1, Н, s
5
)
0 (0, П, s
0
) (1, Л, s
4
)
* (*, П, s
0
) (*, П, s
1
) (*, Л, s
3
) (*, Л, s
4
)
= (=, Л, s
4
) (=, П, s
2
) (=, Л, s
3
)
λ λ 1 1 1 * 1 1 = 1 1 1 1 1 λ λ
s
0
Рис. 32
s
5
Рис. 33

Страницы