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

Рассмотрим примеры частично-рекурсивных функций. Все эти примеры и много других можно найти в [21, 23].

Сложение двух чисел

sum: <x,y> à x+y.

Эта функция является общерекурсивной в силу примитивной рекурсии

sum(x,0) = pr₁(x) = x,

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

Умножение двух чисел

prod: <x,y> à x y.

Используем примитивную рекурсию

prod(x,0) = 0(x) = 0,

prod(x,y+1) = sum(prod(x,y),x).

Усеченное вычитание 1

d(x) = x-1, если x>0,

d(0) = 0.

Эта функция примитивно-рекурсивна, действительно,

d(0) = 0 = 0(x),

d(y+1) = y = pr₂(<x,y>).

Усеченная разность

x¸y = x-y, если x ³ y,

x¸y = 0, если x < y.

Эта функция примитивно-рекурсивна, действительно,

x¸0 = x,

x¸(y+1) = d(x¸y).

Модуль разности

|x-y| = x-y, если x³y,

|x-y| = y-x, если x<y.

Эта функция примитивно-рекурсивна в силу суперпозиции

|x-y| = (x¸y)+(y¸x).

Факториал

Действительно,

0! = 1,

(y+1)! = prod(y!,y+1).

min(x,y) - наименьшее из чисел x и y

В силу суперпозиции: min(x,y) = x¸(x¸y).

Знак числа

sg(x) = 0, если x = 0,

sg(x) = 1, если x>1.

В силу рекурсии

sg(0) = 0,

sg(y+1) = 1.

rm(x, y) - остаток от деления y на x

В силу рекурсии и суперпозиции

rm(x,0) = 0,

rm(x,y+1) = prod(s(rm(x,y)),sg(|x-s(rm(x,y))|)).

Используя функции, для которых уже установлено, что они являются частично-рекурсивными, мы получаем все новые и новые частично-рекурсивные функции. Существуют критерии, которые позволяют установить частичную рекурсивность сразу для обширных классов функций (см., например, 23, с. 135-151).

Используя минимизацию (m-оператор) можно получать частично-определенные функции из всюду определенных функций. Например, полагая f(x,y) есть частично-рекурсивная функция |x-y²|, мы обнаруживаем, что g(x) = my[f(x,y)=0] - не всюду определенная функция

g(x) = , если x есть точный квадрат и неопределена в противном случае.

Таким образом, тривиально используя m-оператор вместе с суперпозицией и рекурсией, можно построить больше функций, исходя из основных, чем только с помощью суперпозиции и рекурсии (так как эти операции порождают из всюду определенных функций - всюду определенные). Существуют, однако, и общерекурсивные (всюду определенные) функции, для построения которых нельзя обойтись без минимизации. Примером такой функции является функция Аккермана [13, с. 53]:

f(0,y) = y+1,

f(x+1,0) = f(x,1),

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

Чистая математика - это такой предмет, где мы не знаем, о чем мы говорим, и не знаем, истинно ли то, что мы говорим.

Бертран Рассел

Человек должен верить, что непонятное можно понять; иначе он нe стал бы размышлять о нем.

В. Гёте