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

Теорема 1. Если функции f(x₁,x₂,…,x_n), g₁ (x₁,x₂,…,x_m), …, g_n (x₁,x₂,…,x_m) правильно вычислимы по Тьюрингу, то правильно вычислима и сложная функция (суперпозиция функций):

φ(x₁,x₂,…,x_n)=f( g₁ (x₁,x₂,…,x_m),…, g_n (x₁,x₂,…,x_m)).

Доказательство: руководствуясь определением композиции машин Тьюринга, нетрудно понять, что если машина F правильно вычисляет функцию f(y), а машина G правильно вычисляет функцию g(x), то композиция этих машин вычисляет суперпозицию этих функций f(g(x)):q₁01^x; G:q01^g(x,y); F:q01^f(g(x,y)).

Рассмотрим более сложную суперпозицию вычислимых функций: φ(x,y)= f(g₁(x,y), g₂(x,y)). Пусть машины F, G₁, G₂ правильно вычисляют функции f, g₁, g₂ соответственно. Сконструируем машину Тьюринга, правильно вычисляющую сложную функцию φ(x,y), пользуясь введенными нами машинами сдвига, транспозиции, копирования и нулевой функции:

q₁01^x01^y;

K₂: 01^x01^yq01^x01^y;

G₁: 01^x01^yq01^g1(x,y);

Ц: 01^g1(x,y) q 01^x01^y;

G₂: 01^g1(x,y) q01^g2(x,y) ;

Б^-:q01^g1(x,y) 01^g2(x,y) ;

F: q01 ^{f(g1(x,y) ,g2(x,y))};

q0→q₀0 q₀01 ^f(g1,g2).

Сконструируйте самостоятельно композицию машин, правильно вычисляющих функцию φ(x,y)= f(g₁(x,y), g₂(x,y), g₃(x,y)). Подстановки указанного вида достаточно специфичны (все функции g имеют одно о тоже число аргументов) и не исчерпывают всевозможных подстановок, которые можно производить над функциями. Но благодаря функциям-проекторам I_mⁿ этот недостаток легко устраним: любая суперпозиция функций в функции может быть выражена через суперпозиции указанного вида и функции-проекторы. В самом деле, например, суперпозиция f(g₁(x₁, x₂), g₂(x₁))может быть в требуемом виде представлена так: f(g₁(x₁, x₂), I₁² (g₂(x₁), g₃(x₁))), где g₃(x₁) – любая функция от х₁. В свою очередь, используя подстановку и функции-проекторы, можно переставлять аргументы в функции:

f(x₂, x₁, x_3,…,x_n)=f(I₂²(x₁, x₂), I₁²(x₁, x₂), x₃, …, x_n);

f(x₁, x₁, x_3,…,x_n)=f(I₁²(x₁, x₂), I₁²(x₁, x₂), x₃, …, x_n);

поэтому можно считать, что теорема полностью доказана.

Сделаем еще один шаг на пути (в каком-то смысле аксиоматического) описания всех функций, вычислимых с помощью машины Тьюринга. Мы докажем, что всякая примитивно рекурсивная функция вычислима с помощью машины Тьюринга. Для этого остается доказать следующую теорему.