Funkcja rekurencyjna – funkcja
która jest obliczalna za pomocą maszyny Turinga. Klasę tych funkcji definiuje się za pomocą mniejszej klasy funkcji pierwotnie rekurencyjnych:
Funkcjami pierwotnie rekurencyjnymi nazywamy funkcje:
zdefiniowana jako ![{\displaystyle {\begin{matrix}Z(n)=0\end{matrix}}}](//wikimedia.org/api/rest_v1/media/math/render/svg/26dcda555149e1c3053ef46c0913f72ce49e3412)
zdefiniowana jako ![{\displaystyle {\begin{matrix}S(n)=n+1\end{matrix}}}](//wikimedia.org/api/rest_v1/media/math/render/svg/1dc9dbf2d1ae261ac733ed372995b777740334e8)
zdefiniowana jako ![{\displaystyle I_{n}^{i}(x_{1},\dots ,x_{n})=x_{i},\ i\leqslant n}](//wikimedia.org/api/rest_v1/media/math/render/svg/524af3845943854254d3f3b9cd81555064e590ed)
oraz wszystkie funkcje zbudowane z funkcji pierwotnie rekurencyjnych za pomocą następujących metod kompozycji:
- Dla danych funkcji
oraz
złożeniem nazywamy funkcję
zdefiniowaną jako ![{\displaystyle h({\overline {n}})=f(g_{1}({\overline {n}}),\dots ,g_{k}({\overline {n}}))}](//wikimedia.org/api/rest_v1/media/math/render/svg/a57e4001b5b5610495e826cbd791a34a4425025c)
- Dla danych funkcji
oraz
złożeniem rekurencyjnym nazywamy funkcję
zdefiniowaną jako ![{\displaystyle {\begin{cases}f({\overline {n}},0)=g({\overline {n}})\\f({\overline {n}},S(m))=h(f({\overline {n}},m),{\overline {n}},m)\end{cases}}}](//wikimedia.org/api/rest_v1/media/math/render/svg/0e0a9e99114bd6280ab02ed9b91bce5bb4dc033d)
Dodając do zbioru możliwych operacji operator minimalizacji otrzymujemy klasę funkcji częściowo rekurencyjnych:
Dla danej funkcji
definiujemy funkcję
w ten sposób, że wartością
jest minimalne y takie, że
jest zdefiniowane, oraz
![{\displaystyle f(y,x_{1},x_{2},\dots ,x_{n})=0.}](//wikimedia.org/api/rest_v1/media/math/render/svg/3ca5de7984517fb57ca2e35aa43436d53fcedc0f)
Ponieważ nie dla wszystkich wartości
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.
Funkcjami elementarnie rekurencyjnymi nazywamy funkcje:
- funkcję następnika,
- funkcję odejmowania ograniczonego
zdefiniowaną jako ![{\displaystyle {\dot {-}}(x,y)={\begin{cases}{0,\ x<y}\\{x-y,\ x\geqslant y}\end{cases}},}](//wikimedia.org/api/rest_v1/media/math/render/svg/60bf70b4bff9c17bef272e3bb232bf57219ad2ae)
zdefiniowaną jako ![{\displaystyle {\begin{matrix}pow(x,y)=x^{y}\end{matrix}}.}](//wikimedia.org/api/rest_v1/media/math/render/svg/2334032bbb1b4ebf851c33c27a32b007d34ffff3)
oraz wszystkie funkcje zbudowane z powyższych trzech za pomocą złożenia funkcji i operatora minimalizacji ograniczonej.
Niech dana będzie pierwotnie rekurencyjna funkcja
Wówczas funkcje
zdefiniowana jako ![{\displaystyle h_{1}({\overline {n}},m)=\sum _{i=0}^{m}f({\overline {n}},i),}](//wikimedia.org/api/rest_v1/media/math/render/svg/f85c963be455868dab4163452204c20dbf2f2d97)
zdefiniowana jako ![{\displaystyle h_{2}({\overline {n}},m)=\prod _{i=0}^{m}f({\overline {n}},i)}](//wikimedia.org/api/rest_v1/media/math/render/svg/18d27241da41fedabf02767c16cb3d8d39ff5e65)
są funkcjami pierwotnie rekurencyjnymi.
Analogicznie twierdzenie zachodzi dla funkcji elementarnie rekurencyjnych.
- Mycka J., Teoria funkcji rekurencyjnych, wrzesień 2000, (dostęp 27 sierpnia 2011).