Оператор примитивной рекурсии

Пусть заданы частичные функции g: Nⁿ  N и h: Nⁿ⁺²  N. Оператором примитивной рекурсии называется оператор, сопоставляющий паре (g, h) такую частичную функцию f: Nⁿ⁺¹  N, что для всех x₁,…,x_n,у    N имеют место равенства:

f(x₁,…,x_n,0)  =  g(x₁,…,x_n);

f(x₁,…,x_n,y+1)  =  h(x₁,…,x_n,y, f(x₁,…,x_n,y)).

Поскольку область определения и значения дополняются отмеченной точкой, то равенство частичных функций означает, что для каждого значения аргумента либо левая, либо правая части равенства определены и равны между собой, либо обе его части не определены. Значение оператора примитивной рекурсии обозначается: f  =  R(g,h). Если g и h определены всюду, то f  =  R(g,h) определена всюду.

Если n  =  0, то для любых числа g    N и частичной функции h: N²  N частичная функция f = R(g,h) определяется с помощью равенств:

f(0)  =  g, f(y + 1)  =  h(y,f(y)).

Функция f называется примитивно рекурсивной, если ее можно получить из простейших функций s, o и Iⁿ_m с помощью операторов суперпозиции и примитивной рекурсии (таким образом, примитивно рекурсивная функция всюду определена.)