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



             

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


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

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

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

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

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

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

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

 code_1(w_1) = \sum_{l=0}^{m} R^l i_l \ code_2(w_2) = \sum_{l=0}^{p} R^l j_l .

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

, *, |}, то для конфигурации 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) - код символа, который пишет

 \mathcal{ M},
когда она в состоянии qi видит символ aj;

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

 \mathcal{ M},
когда она в состоянии qi видит символ aj;

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

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

Пусть при i

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

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

 lf(code_1(w_1),i,j,code_2(w_2))= code_1(w_1^\prime); \\ rt(code_1(w_1),i,j,code_2(w_2))= code_2(w_2^\prime); \\ q(code_1(w_1),i,j,code_2(w_2))= m; \\ a(code_1(w_1),i,j,code_2(w_2))= p.

Покажем, что все эти функции примитивно рекурсивны.


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