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


           

q это следует из того,


Для 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) Объединяя эти случаи получаем, что



( здесь 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(4), Q(4), Lf(4), Rt(4) с помощью совместной рекурсии. Следовательно, по лемме 18.5 они примитивно рекурсивны.

Пусть м.Т.
вычисляет функцию 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. Положим
и
Тогда функция
задает число шагов до перехода
в заключительное состояние на входе x. Эта функция, очевидно, частично рекурсивна. Тогда функция
задает код правой части заключительной конфигурации, имеющий вид Rf(x)-1-1. Отсюда получаем, что



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


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