Пусть C — класс числовых функций,
x ≡ x1,...,xn
— кортеж переменных.
C замкнут относительно композиции,
если из
g, h1 ... hn ∈ C
следует
f(x) = g(h1(x),...,hn(x)) ∈
C.
C замкнут относительно примитивной рекурсии,
если для любых g, h ∈ C
функция f, определяемая равенствами
| f(x, 0) = g(x), | (уравнения рекурсии) |
| f(x, y + 1) = h(x, y, f(x, y)), |
также принадлежит C.
Говорят, функция f определена рекурсией из g и h.
Класс PR примитивно-рекурсивных функций — это наименьший класс числовых функций, содержащий все примитивные функции и замкнутый относительно композиции и примитивной рекурсии.