Частично рекурсивные функции

Функция называется примитивно рекурсивной, если может быть получена из исходных числовых функций с помощью применения конечного числа операций суперпозиции и примитивной рекурсии.

Исходными числовыми функциями являются:

1) нуль-функция: o(x) = 0 при каждом x;

2) функция следования: s(x) = x + 1 при каждом x;

3) функция выбора аргументов: I (x₁, x₂,..., x_n) = x_m при всех x₁, x₂,..., x_n (m = 1, 2, …, n; n = 1, 2, …).

Получение новых функций из уже имеющихся осуществляется с помощью операций суперпозиции и примитивной рекурсии.

1. Операция суперпозиция (подстановка). Пусть даны числовые функции f(x₁, x₂,..., x_n) и g₁(x₁,..., x_m), g₂(x₁,..., x_m), …, g_n(x₁,..., x_m) и пусть h(x₁, x₂,..., x_n) = f(g₁(x₁,..., x_m), g₂(x₁,..., x_m), …, g_n(x₁,..., x_m)). Тогда будем говорить, что функция h получена с помощью подстановки из функций f(x₁, x₂,..., x_n), g₁(x₁,..., x_m), g₂(x₁,..., x_m), …, g_n(x₁,..., x_m).

Пример 2.1. Доказать, что функция s (x₁, x₂,..., x_n) = x_m + 1 примитивно рекурсивна.

Решение. Функция s (x₁, x₂,..., x_n) получается с помощью операции подстановки:

s (x₁, x₂,..., x_n) = s(I (x₁, x₂,..., x_n)) = x_m + 1.

Пример 2.2. Доказать, что функция R(x) = 2 примитивно рекурсивна.

Решение. Функция R(x) получается с помощью двух операций подстановки:

R(x) = s(s(o(x))) = s(s(0)) = s(0+1) = 1+1 = 2.

2. Операция примитивная рекурсия. Пусть даны числовые функции g(x₁,..., x_n) и h(x₁,..., x_n, x_n+1, x_n+2) при n ³ 1. Тогда функцию f(x₁,..., x_n, x_n+1) можно определить как:

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)).

Данные равенства называются схемой примитивной рекурсии.

При n = 0 схема примитивной рекурсии имеет следующий вид:

f(0) = a,

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

где a – постоянная одноместная функция, равная числу a.

Пример 2.3. Доказать, что функция f₊(x,y) = x + y примитивно рекурсивна.

Решение. По схеме примитивной рекурсии получаем:

f₊(x,0) = x + 0 = x = I (x);

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

Функция называется частично рекурсивной, если может быть получена из исходных числовых функций с помощью применения конечного числа операций суперпозиции, примитивной рекурсии и минимизации.

Определим операцию минимизации, также называемую m-оператором. Пусть дана функция y = f(x₁, x₂,..., x_n). Зафиксируем параметры x₁, x₂,..., x_n. Операция минимизации представляет наименьшее число y, такое что

mf(x₁, x₂,..., x_n) = {f(x₁,..., x_n-1, y) = x_n}.

Частично рекурсивные функции определены на множестве целых неотрицательных чисел.

Упражнения

а) Доказать, что функции примитивно рекурсивны:

1. f₂(x) = x + 2.

2. Арифметическое или урезанное вычитание ():

f₃(x) =

f₄(x,y) =

3. Функция сигнум:

4. Отрицание функции сигнум:

5. f₅(x,y) = x × y.

6. f₆(x) = x².

7. f₇(x,y) = x^y.

8. f₈(x,y) = .

9. f₉(x,y) = max(x,y).

10. f₁₀(x,y) = min(x,y).

11. Факториал: f_!(x) = x!.

б) Доказать, что функции частично рекурсивны:

1. Остаток от деления y на x:

rest(x,y) (здесь rest(x,0) = x).

2. Число делителей числа x:

t(x) (здесь t(0) = 0).

3. Сумма делителей числа x:

s(x) (здесь s(0) = 0).

4. Число простых делителей числа x:

lh(x) (здесь lh(0) = 0).

5. Число простых чисел: p(x).

в) Доказать следующие равенства:

1) ;

2) ;

3) ;

4) .