Введение в схемы, автоматы и алгоритмы



             

Частичная рекурсивность функций, вычислимых по Тьюрингу - часть 2


Для q это следует из того, что для любых i, j q(l,i,j,m)=Q(i,j). Определения остальных трех функций зависят от сдвига. При C(i,j)=0 имеем lf(l,i,j,r)=l, rt(l,i,j,r)= r, a(l,i,j,r)=A(i,j).

Если C(i,j)=2, то lf(l,i,j,r)=div(R, l), rt(l,i,j,r)= rR+A(i,j), a(l,i,j,r)=rm(R,l). Если же C(i,j)=1, то lf(l,i,j,r)=lR+A(i,j), rt(l,i,j,r)= div(R, r), a(l,i,j,r)=rm(R,r) Объединяя эти случаи получаем, что

lf(l,i,j,r)= eq(C(i,j),0)l+eq(C(i,j),2)div(R, l)+eq(C(i,j),1)(lR +A(i,j))

( здесь rm(x,y) - это функция, дающая остаток от деления y на x, а div(x,y) - функция целочисленного деления y на x).

Аналогичные представления справедливы и для функций rt(l,i,j,r) и a(l,i,j,r). Следовательно, все эти функции примитивно рекурсивны.

Пусть из данной конфигурации K через t тактов получается конфигурация Kt. Определим коды компонент Kt как функции от компонент K и t :

 A(l,i,j,r,0)=j, Q(l,i,j,r,0)=i, Lf(l,i,j,r,0)=l, Rt(l,i,j,r,0)=r, \\ A(l,i,j,r,t+1)=a(Lf(l,i,j,r,t),Q(l,i,j,r,t),A(l,i,j,r,t),Rt(l,i,j,r,t)), \\ Q(l,i,j,r,t+1)=q(Lf(l,i,j,r,t),Q(l,i,j,r,t),A(l,i,j,r,t),Rt(l,i,j,r,t)), \\ Lf(l,i,j,r,t+1)=lf(Lf(l,i,j,r,t),Q(l,i,j,r,t),A(l,i,j,r,t),Rt(l,i,j,r,t)), \\ Rt(l,i,j,r,t+1)=rt(Lf(l,i,j,r,t),Q(l,i,j,r,t),A(l,i,j,r,t),Rt(l,i,j,r,t)). \\

Это определение задает функции A(4), Q(4), Lf(4), Rt(4) с помощью совместной рекурсии. Следовательно, по лемме 18.5 они примитивно рекурсивны.

Пусть м.Т.

 \mathcal{ M}
вычисляет функцию f(x), (т.е. n=1). Тогда для начальной конфигурации Kx=K0=(
,q0,|,|x-1) code1(w1)=0, code(q0)=0, code(|)=R-1, code2( w2 ) = (R-1)Rx-2+(R-1)R x-3+ … +(R-1)R0=R x-1-1. Положим
 \bar Q(x,t)=Q(0,0,R-1,R^{x-1}-1, t)
и
 \bar{Rt}(x,t)=Q(0,0,R-1,R^{x-1}-1, t).
Тогда функция
 \tau(x)= \mu t(\bar Q(x,t)=1)
задает число шагов до перехода
 \mathcal{ M}
в заключительное состояние на входе x. Эта функция, очевидно, частично рекурсивна. Тогда функция
 \hat{Rt}(x)=\bar{Rt}(x,\tau(x))
задает код правой части заключительной конфигурации, имеющий вид Rf(x)-1-1. Отсюда получаем, что

f(x)= 1 + \log_R(\hat{Rt}(x))+1)=1+\log_R(Rt(0,0,R-1,R^{x-1})+1),

и следовательно, функция f(x) частично рекурсивна.




Содержание  Назад  Вперед