Найти значение. S3(I22, I11,01). В этом случае конечная функция будет двуместной (п = 3 - 1 = 2), следовательно h(х1, х2) = I22(I11, 01) = I22(x1, 0) = 0 .
Примитивная рекурсия
Пусть заданы какие-либо числовые частичные функции: n-местная g(x1,..., хn) и (п + 2)-местная h(x1, ..., xn, k, у). Говорят, что (п + 1)-местная частичная функция f образуется из функций д и h посредством примитивной рекурсии, если для всех натуральных значений х1;..., xn, у справедливо:
Поскольку областью определения функций является множество всех натуральных чисел, частичная функция f, удовлетворяющая условиям (7.1), существует для каждых частичных функций g и h и функция эта будет единственной. Условия (7.1) задают также последовательность определения значений f на различных шагах рекурсии:
Символически примитивная рекурсия обозначается f = R(g,h); в этой записи R рассматривается как символ двуместной частичной операции, определенной на множестве всех частичных функций. Из соотношений (7.2) вытекает, в частности, что если g и h являются всюду определенными, то и f также является всюду определенной. Из (7.2) видно также то важное обстоятельство, что если умеем находить значения функций g и h, то значения функции f(a1,..., an, т + 1) можно вычислять «механически», находя последовательно значения на предыдущих шагах. Введем определение.
Частичная функция f(x1,..., xn) называется примитивно рекурсивной, если ее можно получить конечным числом операций суперпозиции и примитивной рекурсии, исходя лишь из простейших функций S1, 0n и Imn.
Если операции суперпозиции и примитивной рекурсии применить к всюду определенным функциям, в результате будет получена также всюду определенная функция. В частности, все примитивно рекурсивные функции всюду определены.