Funkcja rekurencyjna

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

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

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 funkcji pierwotnie rekurencyjnych za pomocą następujących metod kompozycji:

  • 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[edytuj | edytuj kod]

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

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

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

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

Zobacz też[edytuj | edytuj kod]

Bibliografia[edytuj | edytuj kod]

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