Примитивно-рекурсивные функции

Пусть C — класс числовых функций,
xx1,...,xnкортеж переменных.

C замкнут относительно композиции,
если из g, h1 ... hnC следует
  f(x) = g(h1(x),...,hn(x)) ∈ C.

C замкнут относительно примитивной рекурсии,
если для любых g, hC функция f, определяемая равенствами

f(x, 0) = g(x), (уравнения
рекурсии)
f(xy + 1) = h(xyf(xy)),

также принадлежит C.

Говорят, функция f определена рекурсией из g и h.

Класс PR примитивно-рекурсивных функций — это наименьший класс числовых функций, содержащий все примитивные функции и замкнутый относительно композиции и примитивной рекурсии.