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

Пусть заданы частичные функции 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, 0 и Iⁿ_m с помощью операторов композиции и примитивной рекурсии (таким образом, примитивно рекурсивная функция всюду определена.)

Пример 2

Функция o: N ® N, принимающая постоянные значения o(x)=0, будет примитивно рекурсивной в силу

o(0) = 0;

o(y+1)= I²₂(y, o(y)).

Функция оⁿ: Nⁿ ® N, все значения которой равны нулю, примитивно рекурсивна, ибо она является композицией о ° Iⁿ₁ простейших функций Iⁿ₁: Nⁿ ® N и о: N ® N. Рассмотрим при k ³ 1 функцию c_k: Nⁿ ® N, все значения которой равны k. Функция c_k равна композиции функций оⁿ: Nⁿ ® N и k функций N ® N ®…® N, каждая из которых равна s, c_k = s^k °oⁿ. Стало быть, c_k примитивно рекурсивна.

Пример 3

Функция f: N² ® N, заданная как f(x,y) = x + y, удовлетворяет соотношениям:

f(x,0) = x;

f(x,y + 1) = (x + y) +1 = f(x,y) + 1 = s(f(x,y)).

Положим: g(x) = I¹₁(x) = x, h(x,y,z) = s(z). Так как f(x,0) = g(x) и
f(x,y + 1) = h(x,y,f(x,y)), то f = R(g,h) = R(I¹₁,s ° I³₃). Значит, f – примитивно рекурсивна.

Предложение 1 Для любых примитивно рекурсивных функций f(x₁, …, x_n) и g(x₁, …, x_n) их сумма примитивно рекурсивна.

Доказательство. Вытекает из равенства

f(x₁, …, x_n)+g(x₁, …, x_n)= S(+,f,g) (x₁, …, x_n).

Пример 4

Функция f: N² ® N, заданная как f(x,y) = x×y, удовлетворяет соотношениям:

f(x,0) = 0;

f(x,y + 1) = x ( y + 1) = f(x,y) + x.

Положим: g(x) = o(x), h(x,y,z) = x+z . Так как f(x,0) = o(x) и
f(x,y + 1) = h(x,y,f(x,y)), то f = R(g,h) = R(o, S(+, I³₁,, I³₃). Значит, f – примитивно рекурсивна.

Предложение 2 Для любых примитивно рекурсивных функций f(x₁, …, x_n) и g(x₁, …, x_n) их произведение примитивно рекурсивно.

Пример 5

Рассмотрим функцию: f(x,y) = x^y. Поскольку f(x,0) = 1, и
f(x,y + 1) = x×f(x,y) = g(x,y,f(x,y)), где g(x,y,z) = x×z – примитивно рекурсивная функция (как композиция операции умножения и функции (I³₁, I³₃): N³ ® N²), то f(x,y) примитивно рекурсивна.

Пример 6

Пусть d(x) = max(0,x – 1). Имеют место равенства d(0) = 0 и
d(y + 1) = y = g(y,d(y)), где g(y,z) = I²₁(y,z) = y. Следовательно, d(x) – примитивно рекурсивна.

Пример 7

Пусть r(x,y) = max(0,x – y). Верны соотношения r(x,0) = x и
r(x,y + 1) = d(r(x,y)) = g(x,y,r(x,y)), где g(x,y,z) = d(z) – функция из примера 5. Значит, r(x,y) – примитивно рекурсивна.

Пример 6 показывает, что функция f(x,y) =ôx-yô= r(x,y) + r(y,x) примитивно рекурсивна, как композиция функций x₁ + x₂ и пары функций (r(x,y),r(y,x)): N² ® N² (примитивная рекурсивность функции r(y,x) получается из разложимости r(y,x) = S³(r, I²₂, I²₁)).