2.3 Рекурсивні функції
Кожен алгоритм однозначно ставить у відповідність з вихідними даними результат. Отже, з кожним алгоритмом однозначно пов'язана якась функція, яку він обчислює. На з'ясуванні питання для яких функцій алгоритми існують, а для яких немає заснована теорія рекурсивних функцій.
Основним в ній є те, що всі безліч досліджуваних функцій будується з кінцевого числа вихідних функцій (базису) за допомогою простих операцій, ефективна здійсненність яких досить очевидна. Операції над функціями будемо називати операторами.
2.3.1 Примітивно. рекурсивні функції
До обчислюваної функції можна віднести все константи, тобто 0 і все натуральні числа 1,2. Але можна обійтися 0 і функцією проходження f (x) = x + 1 (x '). Крім того в базис включимо функції тотожності, позначимо сімейство таких функцій: Inm (x1, x2. Xn) = xm (m≤n). Інакше її можна назвати функцією введення фіктивних змінних. Визначимо сімейство операторів суперпозиції. для h (x1. xm), gi (x1. xn), i = 1. m.
Snm (h, g1,? Gm) = h (g1 (x1. Xn). Gm (x1. Xn)) = f (x1. Xn).
Оператор примітивної рекурсії Rn
визначає (n + 1) -Місцеві функцію f через n-місцеву функцію g і (n + 2) -Місцеві функцію h таким чином:
f (x1. xn, 0) = g (x1. xn)
f (x1. xn, y + 1) = h (x1. xn, y, f (x1. xn, y))
Ці формули називаються схемою примітивної рекурсії.
У разі, коли f одномісні, отримуємо таке уявлення схеми
f (0) = c
f (y + 1) = h (y, f (y))
Для обчислення f (x1. Xn, k) знадобиться (k + 1) обчислень за схемою при y = 0,1,2. k.
Функція називається примітивно-рекурсивної, якщо вона може бути отримана з константи 0, функції x? і функцій Inm за допомогою застосування кінцевого числа операторів суперпозиций і схем примітивної рекурсії.
1. Додавання f + (x, y) = x + y - примітивно рекурсивно
f + (x, 0) = x = I11 (x)
f + (x, y + 1) = f + (x, y) + 1 = (f + (x, y)) '
2. Множення f × (x, y) = xy - примітивно рекурсивно,
f × (x, 0) = 0
f × (x, y + 1) = f × (x, y) + x = f × (x, f × (x, y))
3. Піднесення до степеня fexp (x, y) = xy - примітивно рекурсивно
fexp (x, 0) = 1
fexp (x, y + 1) = xy x = f × (x, fexp (x, y))
Визначимо функцію x 0