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

Теорема 2.Функция φ, возникшая примитивной рекурсией из правильно вычислимых на машине Тьюринга функций f и g, сама правильно вычислима на машине Тьюринга.

Доказательство: Для краткости записей будем считать, что функция φ связана с функциями f и g следующим образом:

φ(x,0)=f(x),

φ(x,i+1)=g(x, φ(x,i)).

Обозначим F и G – машины Тьюринга, правильно вычисляющие функции f и g соответственно. Пусть x,y – произвольные натуральные числа. Требуется сконструировать машину Тьюринга, вычисляющую значение φ(x,y). Как мы уже отмечали, для вычисления φ(x,y) предстоит вычислить y+1 значений φ(x,0), φ(x,1),…, φ(x,y-1), φ(x,y).

Начальная конфигурация такова: q₁01^x01^y0. Применим к ней следующую последовательность машин Тьюринга: Б⁺ВГВ Б⁺F. В результате получим последовательность конфигураций:

q₁01^x01^y0;

Б⁺:01^x q 01^y0;

В: 01^y q 01^x0;

Г: 01^y q 01^x 01^x 0;

В: 01^x q 01^y 01^x 0;

Б⁺:01^x 01^yq 01^x 0;

F: 01^x 01^yq_α 01^φ⁽^x^,0)0;

На последнем шаге, применив машину, вычисляющую функцию f(x), к конфигурации q01^x, мы получим значение f(x), которое, согласно схеме примитивной рекурсии для φ, есть φ(x,0). Теперь мы можем приступить к вычислению φ(x,1), используя второе соотношение схемы примитивной рекурсии:

φ(x,1)=g(x, φ(x,0)).

Для этого применим сначала к последней конфигурации команды:

q_α0→ q_α₊₁0Л; q_α1→ q_α₊₂0. В результате получим конфигурацию: 01^x01^y^-1 q_α₊₂001^φ⁽^x^,0)0. Теперь нужно подготовить ленту машины к применению машины G, вычисляющей значение g(x,φ(x,0)), то есть необходимо получить на ленте конфигурацию q01^x01^φ⁽^x^,0). Для этого применим к конфигурации 01^x01^y^-1 q_α₊₂001^φ⁽^x^,0)0 последовательность машин АБ^-ВБ⁺ВГВБ^-ВБ⁺Б⁺ВБ^-. Получим последовательность конфигураций:

01^x01^y^-1 q_α₊₂ 001^φ⁽^x^,0)0;

А: 01^x01^y^-1 q 01^φ⁽^x^,0)00;

Б^-:01^xq01^y^-1 01^φ⁽^x^,0);

В: 01^y^-1q01^x 01^φ⁽^x^,0);

Б⁺:01^y^-101^x q 01^φ⁽^x^,0);

В: 01^y^-101^φ⁽^x^,0) q 01^x;

Г: 01^y^-101^φ⁽^x^,0) q 01^x01^x;

В: 01^y^-101^x q 01^φ⁽^x^,0) 01^x;

Б^-:01^y^-1 q 01^x 01^φ⁽^x^,0) 01^x;

В: 01^xq 01^y^-1 01^φ⁽^x^,0) 01^x;

Б⁺:01^x01^y^-1 q 01^φ⁽^x^,0) 01^x;

Б⁺:01^x01^y^-1 01^φ⁽^x^,0) q 01^x;

В: 01^x01^y^-1 01^xq 01^φ⁽^x^,0);

Б^-:01^x01^y^-1 q 01^x01^φ⁽^x^,0).

Теперь мы можем применить машину G и вычислить значение

φ(x,1)=g(x, φ(x,0)) : 01^x01^y^-1 q_β 01^φ⁽^x^,1).

Применим в этой конфигурации команду: q _β0→q_α0, зацикливающую программу. Получим конфигурацию:

01^x01^y^-1 q_α 01^φ⁽^x^,1).

Начинается следующий цикл, осуществляемый командами, идущими после первого появления состояния q_α. Этот цикл преобразует конфигурацию вида 01^x01^y^-ⁱ q_α 01^φ⁽^x^,ⁱ⁾ в конфигурацию 01^x01^y^-(ⁱ⁺¹⁾ q_β 01^φ⁽^x^,ⁱ⁺¹⁾, при условии, что y>i. Команда q _β0→q_α0 зацикливает программу, и в результате работы цикла параметр y-i будет понижаться до тех пор, пока не получится конфигурация: 01^x0 q_α 01^φ⁽^x^,^y⁾, которая в силу команды q _α0→q_α₊₁0Л перейдет в конфигурацию 01^xq_α₊₁ 001^φ⁽^x^,^y⁾.

Дополнительные команды q _α₊₁0→q_β₊₁0, А, В, О, В, Б^-, А создают на ленте требуемую конфигурацию q₀01^φ⁽^x^,^y⁾, доказывающую, что функция φ(x,y) правильно вычислена на машине Тьюринга. Теорема доказана.