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


           

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


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

Теорема 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’).

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

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