Отыскать значение. S³(I₂², I₁¹,0¹). В данном случае конечная функция будет двуместной (п = 3 — 1 = 2), как следует h(х₁, х₂) = I₂²(I₁¹, 0¹) = I₂₂(x₁, 0) = 0 .

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

Пусть заданы какие-либо числовые частичные функции: n-местная g(x₁,…, х_n) и (п + 2)-местная h(x₁, …, x_n, k, у). Молвят, что (п + 1)-местная частичная функция f появляется из функций д и h средством примитивной рекурсии, если для всех натуральных значений х_1;…, x_n, у справедливо:

Так как областью определения функций является огромное количество всех натуральных чисел, частичная функция f, удовлетворяющая условиям (7.1), существует для каждых частичных функций g и h и функция эта будет единственной. Условия (7.1) задают также последовательность определения значений f на разных шагах рекурсии:

Символически примитивная рекурсия обозначается f = R(g,h); в этой записи R рассматривается как знак двуместной частичной операции, определенной на огромном количестве всех частичных функций. Из соотношений (7.2) вытекает, а именно, что если g и h являются везде определенными, то и f также является везде определенной. Из (7.2) видно также то принципиальное событие, что если умеем отыскивать значения функций g и h, то значения функции f(a₁,…, a_n, т + 1) можно вычислять «механически», находя поочередно значения на прошлых шагах. Введем определение.

Частичная функция f(x₁,…, x_n) именуется примитивно рекурсивной, если ее можно получить конечным числом операций суперпозиции и примитивной рекурсии, исходя только из простых функций S¹, 0ⁿ и I_mⁿ.

Если операции суперпозиции и примитивной рекурсии применить к везде определенным функциям, в итоге будет получена также везде определенная функция. А именно, все примитивно рекурсивные функции везде определены.