Funkcja rekurencyjna

Brak wersji przejrzanej

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:

Spis treści

1 Funkcja pierwotnie rekurencyjna
2 Funkcja częściowo rekurencyjna
- 2.1 Funkcja rekurencyjna
3 Funkcja elementarnie rekurencyjna
4 Twierdzenie o zamkniętości funkcji pierwotnie rekurencyjnych ze względu na sumę i iloczyn
5 Przykłady funkcji rekurencyjnych
6 Zobacz też
7 Literatura

[edytuj] 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\leq 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.$

[edytuj] 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\le 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.

[edytuj] 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.

[edytuj] 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\geq y}}\right.$

funkcję potęgowania

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

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

[edytuj] 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.

[edytuj] Przykłady funkcji rekurencyjnych

[edytuj] Zobacz też

[edytuj] Literatura

Mycka J. Teoria funkcji rekurencyjnych. Wrzesień 2000. [1] (dostęp 1 października 2006)

Źródło: „http://pl.wikipedia.org/wiki/Funkcja_rekurencyjna”

Kategorie: Teoria obliczeń • Rekursja