Частично рекурсивная функция

Частично рекурсивная функция - частичная функция f, полученная из простейших функций 0, s, $~I_m^n$ конечным числом операций подстановки, примитивной рекурсии и минимизации.

Простейшие (базисные) функции:

• Нуль-функция

$~0(x)=0$

• Функция следования

$~s(x)=x+1$

• Функция выбора аргумента

$~I_m^n (x_{1},x_{2},\cdots,x_{n})=x_m$

Операции над базисными функциями

• Подстановка (суперпозиция).

$~f_1(x_1,...,x_n), ...f_2(x_1,...,x_n)$

$~g(f_1(x_1,...,x_n), ...f_2(x_1,...,x_n))$

Операцией подстановки называется операция вида $~S(g,f_1,...,f_n)$

• Примитивная рекурсия.

Операцией примитивной рекурсии называется операция вида R(g,h), где для всех натуральных значений $~x_1,x_2,...x_n$ выполняется:

$~f(x_1,x_2,...x_n,0) = g(x_1,x_2,...x_n)$

$~f(x_1,x_2,...x_n,y+1) = h(x_1,x_2,...x_n,y,g(x_1,x_2,...x_n))$

• Минимизация.

Операцией минимизации называется операция вида $~M_y(f(x_1,x_2,...x_n,y)=x_{n+1})$, где вычисляется значение $~f_1(x_1,...,x_n,0)$, потом $~f_1(x_1,...,x_n,1)$ и так далее до тех пор, пока на шаге k не получим $~x_{n+1}$, число k и будет результатом действия операции.