Функция f назы­вается примитивно-рекурсивной¹¹, если она является одной из простейших функций¹⁰ s, C¹₀, Jⁿ_m или может быть получена из простейших функций с помощью конечного числа операторов подстановки и примитивной рекурсии. Определение примитивно-рекурсивной функции — индуктивное: определены исходные примитивно-рекурсивные функции s, C¹₀, Jⁿ_m и даны правила построения любых других при­митивно-рекурсивных функции.

Операторы подстановки и примитивной рекурсии, при­мененные ко всюду определенным функциям, дают также всюду определенные функции, поэтому все примитивно-рекурсивные функции всюду определенные.

Пример 6. Показать, что n-местная функция-константа явля­ется примитивно-рекурсивной. Действительно

C_aⁿ(x₁,…, x_n)=s(s(…s(C₀¹(J₁ⁿ(x₁,…, x_n))))…)),

где s(x)=x+1. Таким образом, функция С_а выражается с помощью подстановок через примитивно-рекурсивные функции s, С¹₀ , Jⁿ₁ и, сле­довательно, является примитивно-рекурсивной.

Пример 7. Функция f (х, у)=х+у может быть построена по схеме примитивной рекурсии:

f(x, 0)=x=J₁¹(x),

f(x, y+1)=s(f(x, y))=h(x, y, z),

т. е. f(x, у) возникает примитивной рекурсией из примитивно-рекурсивных функций g(x)=J¹₁(x) и h(x, у, z)=s(z).

Пример 8. Назовем сложение, умножение и возведение в сте­пень соответственно действиями нулевой, первой и второй ступеней и обозначим соответственно

Р₀(х,у)=х+у, Р₁(х,у)=ху, Р₂{х,у)=х^y.

Нетрудно заметить, что при n = 1, 2

P_n(x,0)=g(x),

где g(x) =0 при n=1 и g(x) =1 при п=2,

P_n(x,y+1)=P_n-1(x, Р_п(х,y)).

Отсюда видно, что функция Р_n(х, у) (п =1,2) возникает примитив­ной рекурсией из функций g(x) и h (х, у, z)=P_n-1 (х, z). Следова­тельно, функции P₁ и P₂  — примитивно-рекурсивные. Можно продол­жить эту последовательность функций в сторону высших ступеней, полагая (при п =2, 3, ...)

P_n(x,0)=1,

P_n(x,y+1)=P_n-1(x,P_n(x,y)).

Например, функция третьей ступени имеет вид:

P₃(x, 0)=1,

P₃(x, 1)=x,

P₃(x, 2)=x^x,

P₃(x, 3)=x,

……………,

 Все функции Р_n(х, у) являются примитивно-рекурсивными.

Нетрудно показать, что примитивно-рекурсивными являются следующие функции¹²:

Усеченная разность

xy=

Абсолютная величина разности

Знак x

Sg x=

Функция

 x=

Представление примитивно-рекурсивной функции с помощью операторов подстановки и примитивной рекурсии, примененных к функциям s, C¹₀, Jⁿ_m, по существу определяет способ вычисления значений функции. Поэтому доказательство примитивной рекурсивности какой-либо функции является одновременно доказательством существования алгоритма вычисления функции.

Функция f называется частично-рекурсивной¹³, если она может быть получена из функций s, C₀¹, J_mⁿ с помощью конечного числа операторов подстановки, примитивной рекурсии и минимизации. Из определения вытекают следующие свойства частично-рекурсивных функций.

1. Каждая примитивно-рекурсивная функция является также и частично-рекурсивной.

2. Класс частично-рекурсивных функций шире класса примитивно-рекурсивных функций, так как все примитивно-рекурсивные функции всюду определенные, а среди частично-рекурсивных функций есть функции, не всюду определенные. Например, функции Sg^-1, s^-1 или нигде не определенная функция f (х) = m _z(х +1 + z = 0).

Примеры частично-рекурсивных функций.

1. Частичная функция х—у может быть представлена в виде

x – y = m _z(y+z=x),

а функция у+г является примитивно-рекурсивной, следовательно, функция х – y - частично-рекурсивная.

2. Функция x/y = m _z(yz=x) , где yz - примитивно-рекурсивная функция; следовательно, функция x/y - частично-рекурсивная.

3. Пусть f(x) - примитивно-рекурсивная функция и пусть a₁, …, a_n — некоторые натуральные числа. Тогда

g(x)=f(x)-- -…-

— частично-рекурсивная функция, совпадающая с функ­цией f(х) всюду, кроме точек x= a₁, …, a_n, в которых g(x) может быть не определена.

Понятие частично-рекурсивной функции является одним из основных понятий теории алгоритмов. Какие бы классы алгоритмов до сих пор не строились, во всех случаях оказывалось, что числовые функции, вычисляемые посредством этих алгоритмов, были частично-рекурсивными. Поэтому общепринятым является тезис Черча относительно частично-рекурсивных функций: класс алгоритмически вычислимых частичных числовых функций совпадает с классом всех частично-рекурсивных функций.

Для каждой частично-рекурсивной функции f суще­ствует вычислительный процесс, посредством которого любое натуральное число х перерабатывается в значение f(х) функции f. Этот процесс не дает определенного результата, тогда и только тогда, когда значение функции f в точке х не определено.

Рассмотрим способ полу­чения всюду определенных частично-рекурсивных функций. Введем оператор слабой минимизации М^l следую­щим образом:

M^lf=

Функции¹⁴, которые можно получить из простейших функций s, C¹₀, Jⁿ_m применением конечного числа операторов подстановки, примитивной рекурсии и слабой минимиза­ции, называются общерекурсивными.

Так как операторы R, M^l, S^l, примененные ко всюду определенным функциям либо ничего не дают, либо дают снова функции, всюду определенные, то все общерекурсивные функции - всюду определенные. Если результат применения оператора слабой минимизации определен, то он совпадает с результатом применения оператора обычной минимизации. Поэтому общерекурсивные функции являются всюду определенными частично-рекурсивными функциями;

верно и обратное: каждая всюду определенная частично-рекурсивная функция — общерекурсивна.