Составители:
Рубрика:
Функции j′(j,s,m,n), s′(j,s,m,n), m′(j,s,m,n), n′(j,s,m,n) получены
суперпозицией рекурсивных функций, поэтому они рекурсивны.
∼
Теперь мы можем ввести в рассмотрение функции Q
(t,j,s,m,n),
дающие номер состояния, в которое перейдет машина из начальной
конфигурации <j,s,m,n> через t тактов. Введем также функции
S
∼
(t,j,s,m,n), M
∼
(t,j,s,m,n), N
∼
(t,j,s,m,n), дающие номера остальных
элементов четверки через t тактов. Введенные функции
удовлетворяют рекурсивным соотношениям:
Q
∼
(0,j,s,m,n)=j,
∼
(0,j,s,m,n)=s,
S
M
∼
(0,j,s,m,n)=m,
N
∼
(0,j,s,m,n)=n,
Q
∼
(t+1,j,s,m,n)=Q(Q
∼
(t,j,s,m,n),A
∼
(t,j,s,m,n)),
∼
S
(t+1,j,s,m,n)=s′(Q
∼ ∼
(t,j,s,m,n),S (t,j,s,m,n),M
∼
(t,j,s,m,n),N
∼
(t,j,s,m,n)),
M
∼
(t+1,j,s,m,n)=m′(Q
∼ ∼
(t,j,s,m,n),S (t,j,s,m,n),M
∼
(t,j,s,m,n),N
∼
(t,j,s,m,n)),
N
∼
(t+1,j,s,m,n)=n′(Q
∼ ∼
(t,j,s,m,n),S (t,j,s,m,n),M
∼
(t,j,s,m,n),N
∼
(t,j,s,m,n)).
Выписанные формулы определяют схему совместной рекурсии
функций Q
∼ ∼
, S , M
∼
, N
∼
. Совместная рекурсия равносильна простой
рекурсии [9, 14]. Поскольку функции Q, s′, m′, n′ рекурсивны,
функции Q
∼ ∼
, S , M
∼
, N
∼
также рекурсивны. Таким образом, получена
система рекурсивных функций, позволяющих найти конфигурацию,
в которую переходит машина Тьюринга из начальной конфигурации
через t тактов. Остается только доказать частичную рекурсивность
функции f(x), вычисляемой машиной Тьюринга.
Пусть функция f(x) вычисляется машиной Тьюринга с
начальной конфигурацией …Λq
a
1 s
c c c c
0 1 2 3
Λ…, где цепочка
a
s
c c c c
0 1 2 3
представляет значение аргумента x. Для
арифметизированной записи начальной конфигурации <1, s(x), 0,
n(x)> имеем m(x)=0, а номера обозреваемого символа s(x) и n(x)
определяются значением аргумента x. Тогда можно записать
выражение для номера состояния через t тактов
161
Страницы
- « первая
- ‹ предыдущая
- …
- 75
- 76
- 77
- 78
- 79
- …
- следующая ›
- последняя »
