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

В этом параграфе покажем, как можно промоделировать работу машины Тьюринга, используя частично рекурсивные определения.

Теорема 10.3. Всякая арифметическая функция, вычислимая на машинах Тьюринга, является частично рекурсивной функцией.

Доказательство этой теоремы - дополнительный материал, который можно при первом чтении опустить.

Доказательство Пусть м.Т.

вычисляет функцию f(x1,…, xn). Пусть также Q ={q0,q1,… ,q k-1 }, qf=q1 и ? = {a0=, a1, … , a R-1= | }. Предположим также, не ограничивая общности, что никогда не пишет пустой символ (как перестроить программу произвольной м.Т., чтобы она удовлетворяла этому условию ?).

Определим кодирование элементов конфигураций

целыми числами. Пусть конфигурация имеет вид K=(w1,qi,aj,w2), где - слово на ленте левее головки, qi - состояние м.Т., aj - наблюдаемый в данной конфигурации символ и w2= aj0aj1 … ajp} - слово на ленте правее головки. Кодом символа aj ? будет число j, кодом состояния qi - число i. Слова w1 и w2 будем рассматривать как числа в R-ичной системе счисления, читаемые в противоположных направлениях (из наших предположений следует, что im 0 при m >0 и jp 0 при p>0) :

Например, если ?= {

, *, |}, то для конфигурации K=(|**,q3,|,* | |) имеем code1(w1)=30 1+31 1+ 32 2= [211]3=22 и code2(w2)=30 1+ 31 2 +32 2= [221]3=25. По программе P определим следующие табличные функции, кодирующие ее команды:

A(i,j) - код символа, который пишет

когда она в состоянии qi видит символ aj;

Q(i,j) - код состояния, в которое переходит

когда она в состоянии qi видит символ aj;

C(i,j) - код направления сдвига головки

когда она в состоянии qi видит символ aj (0 - на месте, 1 - вправо, 2 - влево).

Пусть при i

k или j R эти функции принимают какое-нибудь фиксированное значение (например, 0). Тогда по лемме 18.1 все они примитивно рекурсивны.

Определим функции, которые по кодам компонент одной конфигурации K=(w1,qi,aj,w2) вычисляют коды компонент следующей конфигурации K’=(w1’,qm,ap,w2’).

Покажем, что все эти функции примитивно рекурсивны.
Для 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) частично рекурсивна.


Содержание раздела

---