Составители:
Рубрика:
Программирование функций следования, константы ноль и
тождества. Функции следования S(x)=x+1=x' и константы ноль
0(x)=0 реализуются достаточно просто [14]. Функция тождества
реализуется машиной Тьюринга, способной вести
счет до n, для этого головка машины должна иметь достаточное
число состояний, превышающее n.
()
mn
n
m
xxxI =,...,
1
Утверждение 4.2. Любая функция, вычислимая на машине
Тьюринга, частично-рекурсивна.
Докажем, что всякая функция, вычислимая по Тьюрингу, может
быть смоделирована ЧР-схемой.
Для этого будем использовать прием, называемый
арифметизацией машины Тьюринга. Арифметизация состоит в том,
что нечисловые параметры (объекты, состояние головки)
нумеруются натуральными числами, что позволяет выразить
преобразования конфигураций машины Тьюринга через
арифметические операции.
Рассмотрим машину Тьюринга с ленточным алфавитом A={a
0
,
a
, …, a } и состояниями Q={q , q , …, q
k-1 r-11 0 1
}. Будем считать, что
a
=Λ (пробел). Букве a
s0
(s = 0, 1, …, k-1) сопоставим цифру i k-
ичной системы счисления. Будем также считать, что q
1
– начальное
состояние, q
– заключительное состояние. Состоянию q
j0
сопоставим
число j.
Рассмотрим произвольную конфигурацию
(4.1)
…Λb
b b b q
3 2 1 0 j
a
s
c c c c Λ… .
0 1 2 3
Содержимое ленты для рассматриваемой конфигурации можно
представить тройкой чисел <s,m,n>, где
s – номер обозреваемого символа a
s
;
m = b
∑
∞
=0i
i
k
i
, n =
∑
∞
=0i
i
c
i
k – k-ичная запись чисел,
представляющих содержимое ленты соответственно слева и справа
от обозреваемого символа.
Числа m и n содержат конечное число цифр, отличных от нуля,
поэтому арифметизированное представление содержимого
бесконечной ленты заполнено нулями за пределами активной зоны.
158
Страницы
- « первая
- ‹ предыдущая
- …
- 72
- 73
- 74
- 75
- 76
- …
- следующая ›
- последняя »
