Составители:
Рубрика:
это последнее преобразование не выходит за рамки рекурсивной
схемы.
Следовательно, функции, вычисляемые на машине Тьюринга,
являются частично-рекурсивными. Доказательство закончено.
4.5. Универсальные машины Тьюринга
и алгоритмическая разрешимость
Метод Геделя. Курт Гедель [3, 8, 9, 15] предложил числовое
кодирование математических объектов. Рассмотрим один из
возможных способов такого кодирования - нумерации машин
Тьюринга.
+ +
Команды qa → a
Dq машины будем кодировать цифрами
восьмеричной системы счисления. Рассмотрим машину Тьюринга с
алфавитом состояний Q={q
, q , …, q
r-10 1
} и ленточным алфавитом
A={a
, a , …, a }, где a
k-10 1 0
= Λ - символ разделителя. Для
кодирования индексов используем двоичную систему счисления с
алфавитом {0
,1 }, где 0 – двоичный ноль, 1
2 2 2 2
–двоичная единица.
Поставим в соответствие символам Λ, a, q, , u, Л, П, Н восьмеричные
цифры:
символ . . . Λ a q 0
1 Л П Н
2 2
цифра . . . 0 1 2 3 4 5 6 7.
Например, команда q
a → a Пq
3 5 4 7
будет закодирована как
восьмеричное число, не содержащее нулей:
2441434143362444.
Роль разделителей между кодами q
, a
i j
и D играют цифры 1, 2, 5, 6 и
7. Каждой команде машины Q
k
поставим в соответствие ее
геделевский номер (шифр), а затем расположим эти номера в порядке
возрастания
Ш(Q
) Ш(Q ) … Ш(Q ).
n1 2
Таким образом построенная последовательность (геделевский номер
машины) z=Ш(Q
)Ш(Q )…Ш(Q
n1 2
) обеспечивает однозначность
кодирования и декодирования машин Тьюринга. Процедура
163
Страницы
- « первая
- ‹ предыдущая
- …
- 77
- 78
- 79
- 80
- 81
- …
- следующая ›
- последняя »
