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

UptoLike

ВУЗ: 

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

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

Рубрика: 

Математическая Логика и Теория Алгоритмов стр. 54 из 64
© 2003 Галуев Геннадий Анатольевич
10
rqxq
n
32
rqxq
n
201
rqxq
4003
qxxq
. . . . . . . . . . . . . . . .
21
rqxq
n
403
qxxq
n
Машины
lrx
i
,, примем за элементарные МТ. Тогда, например, МТ пункта г)
можно собрать из трех машин r и машины
)0(
=
ix
i
.
Пусть
n
MM ,...,
1
некоторые элементарные МТ с общим алфавитом Х. Диаграмма
МТ включает помимо символов элементарных машин символ • (точка) и стрелки,
взвешенные(помеченные) буквами алфавита Х. Причем символ • (точка) может встре-
чаться в ДТ только один раз (он определяет начало работы), а из любого символа
машины может выходить не более одной стрелки
, помеченной одной и той же буквой.
Тогда можно заменить таблицу Тьюринга для(например) МТ из
г) следующей диаграммой
Изображение диаграмм можно упростить следующим образом . заменим все
стрелки для всех j=0,1,…,n одной стрелкой без букв. Если среди всевозможных стре-
лок для всех j=0,1,…,n отсутствует лишь некоторая, взвешенная (помеченная) буквой
j
x
, то заменяем все стрелки одной, указав над ней
j
x
≠
. опустим точку, если она со-
единена всеми стрелками только с одним символом. Опустим непомеченные стрелки
между двумя символами и будем писать
n
M
вместо
MMM ...
−
−
.(n раз). Тогда, ука-
занная выше ДТ примет вид
0
3
xr
.
Из такого способа построения ДТ следует, что переход от таблицы Тьюринга к
ДТ осуществляется однозначно. Для этого требуется выполнить следующие условия:
заменить каждый символ элементарной МТ соответствующей ей таблицей; ввести пе-
реобозначение состояний в командах всех элементарных машин; ввести сквозную
нумерацию в полученной обобщенной таблице.
Машины Тьюринга и вычислимые функции.
Пусть задана некоторая МТz с состояниями
m
qqq ,...,,
10
и натуральный ряд чисел
N (включая ноль). Поставим в соответствие каждой
),...,,(
21 n
aaakn − , где
niNa
i
,...,2,1, =∈ некоторую конфигурацию
n
aaaq ...
2101
=
α
. Если для МТ существует вы-
числение, начинающееся в конфигурации
1
α
и доходящее до заключительной конфи-
гурации
pp
α
α
α
α
,...,,:
21
, то число
Np ∈
, сопоставляемое
p
α
, есть значение функции от
z и начальной n-ки, то есть
),...,,(
21 nz
aaap
ψ
= . Если не существует такого числа р, что
конфигурация
p
α
является заключительной, то функция
z
ψ
не определена для рас-
сматриваемой n-ки и МТz работает бесконечно. Таким образом, исходя из МТz, мы
пришли к функции с областью определения на множестве
n
N
(или может быть на не-
n
x
.
.
.
0
x
n
x
.
.
.
0
x
n
x
.
.
.
0
x
n
x
.
.
.
0
x
0
x

Страницы