Funkcja rekurencyjna

W informatyce i logice formalnej, pojęcie funkcja rekurencyjna określa funkcję $\mathbb{N}^i\rightarrow\mathbb{N}$ która jest obliczalna za pomocą maszyny Turinga. Klasę tych funkcji definiuje się za pomocą mniejszej klasy funkcji pierwotnie rekurencyjnych:

Funkcja pierwotnie rekurencyjna

Funkcjami pierwotnie rekurencyjnymi nazywamy funkcje:

• Funkcja zerowa

$Z:\mathbb{N}\rightarrow\mathbb{N}$, zdefiniowana jako $\begin{matrix}Z(n)=0\end{matrix}$

• Funkcja następnika

$S:\mathbb{N}\rightarrow\mathbb{N}$, zdefiniowana jako $\begin{matrix}S(n)=n+1\end{matrix}$

• Funkcja rzutowania

$I^i_n:\mathbb{N}^n\rightarrow\mathbb{N}$, zdefiniowana jako $I^i_n(x_1,\dots,x_n)=x_i,\ i\leqslant n$

oraz wszystkie funkcje zbudowane z powyższych za pomocą:

• Złożenia funkcji

Dla danych funkcji $f:\mathbb{N}^k\rightarrow\mathbb{N}$ oraz $g_1,\dots,g_k:\mathbb{N}^n\rightarrow\mathbb{N}$, złożeniem nazywamy funkcję

$h:\mathbb{N}^n\rightarrow\mathbb{N}$, zdefiniowaną jako $h(\overline{n})=f(g_1(\overline{n}),\dots,g_k(\overline{n}))$

• Rekursji prostej

Dla danych funkcji $g:\mathbb{N}^{n}\rightarrow\mathbb{N}$ oraz $h:\mathbb{N}^{n+2}\rightarrow\mathbb{N}$, złożeniem rekurencyjnym nazywamy funkcję

$f:\mathbb{N}^{n+1}\rightarrow\mathbb{N}$ zdefiniowaną jako $\left\{{{f(\overline{n},0)=g(\overline{n})}\atop{f(\overline{n},S(m))=h(f(\overline{n},m),\overline{n},m)}}\right.$

Funkcja częściowo rekurencyjna

Dodając do zbioru możliwych operacji operator minimalizacji otrzymujemy klasę funkcji częściowo rekurencyjnych:

• Operator minimalizacji

Dla danej funkcji $f:\mathbb{N}^{n+1}\rightarrow\mathbb{N}$, definiujemy funkcję $h:\mathbb{N}^n\rightarrow\mathbb{N}$ w ten sposób, że wartością $h(x_1,x_2,\ldots,x_n)$ jest minimalne y takie, że

$\forall_{x\leqslant y}f(x,x_1,x_2,\ldots,x_n)$ jest zdefiniowane, oraz

$f(y,x_1,x_2,\ldots,x_n)=0$.

Ponieważ nie dla wszystkich wartości $x_1, \ldots x_n$ takie y musi istnieć, funkcje częściowe rekurencyjne mogą być (w przeciwieństwie do funkcji pierwotnie rekurencyjnych) funkcjami częściowymi.

Funkcja rekurencyjna

Funkcję częściowo rekurencyjną, która jest zdefiniowana dla każdego argumentu, nazywamy funkcją rekurencyjną

Przykładem funkcji która jest rekurencyjna, ale nie jest pierwotnie rekurencyjna, jest funkcja Ackermanna.

Funkcja elementarnie rekurencyjna

Funkcjami elementarnie rekurencyjnymi nazywamy funkcje:

• funkcję następnika
• funkcję odejmowania ograniczonego

$\dot{-}:\mathbb{N}^2\rightarrow\mathbb{N}$, zdefiniowaną jako $\dot{-}(x,y)=\left\{ {{0,\ x < y}\atop{x-y,\ x\geqslant y}}\right.$

• funkcję potęgowania

$pow:\mathbb{N}^2\rightarrow\mathbb{N}$, zdefiniowaną jako $\begin{matrix}pow(x,y)=x^y\end{matrix}$

oraz wszystkie funkcje zbudowane z powyższych trzech za pomocą złożenia funkcji i operatora minimalizacji ograniczonej.

Twierdzenie o zamkniętości funkcji pierwotnie rekurencyjnych ze względu na sumę i iloczyn

Niech dana będzie pierwotnie rekurencyjna funkcja $f:\mathbb{N}^{n+1}\rightarrow\mathbb{N}$. Wówczas funkcje

$h_1:\mathbb{N}^{n+1}\rightarrow\mathbb{N}$, zdefiniowana jako $h_1(\overline{n},m)=\sum^m_{i=0}f(\overline{n},i)$,

$h_2:\mathbb{N}^{n+1}\rightarrow\mathbb{N}$, zdefiniowana jako $h_2(\overline{n},m)=\prod^m_{i=0}f(\overline{n},i)$

są funkcjami pierwotnie rekurencyjnymi.

Analogicznie twierdzenie zachodzi dla funkcji elementarnie rekurencyjnych.

Przykłady funkcji rekurencyjnych

• symbol Newtona
• ciąg Fibonacciego
• funkcja Ackermanna

Zobacz też

• zbiór rekurencyjny
• teoria rekursji
• teoria obliczeń
• złożoność obliczeniowa.

Bibliografia

• Mycka J. Teoria funkcji rekurencyjnych. Wrzesień 2000. [1] (dostęp 27 sierpnia 2011)