Funkcja rekurencyjna

Funkcja rekurencyjna – funkcja $\mathbb {N} ^{i}\to \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\colon \mathbb {N} \to \mathbb {N} ,

zdefiniowana jako

{\begin{matrix}Z(n)=0\end{matrix}}

Funkcja następnika

S\colon \mathbb {N} \to \mathbb {N} ,

zdefiniowana jako

{\begin{matrix}S(n)=n+1\end{matrix}}

Funkcja rzutowania

I_{n}^{i}\colon \mathbb {N} ^{n}\to \mathbb {N} ,

zdefiniowana jako

I_{n}^{i}(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\colon \mathbb {N} ^{k}\to \mathbb {N}

oraz

g_{1},\dots ,g_{k}\colon \mathbb {N} ^{n}\to \mathbb {N} ,

złożeniem nazywamy funkcję

h\colon \mathbb {N} ^{n}\to \mathbb {N} ,

zdefiniowaną jako

h({\overline {n}})=f(g_{1}({\overline {n}}),\dots ,g_{k}({\overline {n}}))

Rekursji prostej

Dla danych funkcji

g\colon \mathbb {N} ^{n}\to \mathbb {N}

oraz

h\colon \mathbb {N} ^{n+2}\to \mathbb {N} ,

złożeniem rekurencyjnym nazywamy funkcję

f\colon \mathbb {N} ^{n+1}\to \mathbb {N}

zdefiniowaną jako

{\begin{cases}f({\overline {n}},0)=g({\overline {n}})\\f({\overline {n}},S(m))=h(f({\overline {n}},m),{\overline {n}},m)\end{cases}}

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\colon \mathbb {N} ^{n+1}\to \mathbb {N} ,$ definiujemy funkcję $h\colon \mathbb {N} ^{n}\to \mathbb {N}$ w ten sposób, że wartością $h(x_{1},x_{2},\dots ,x_{n})$ jest minimalne y takie, że

\forall _{x\leqslant y}f(x,x_{1},x_{2},\dots ,x_{n})

jest zdefiniowane, oraz

f(y,x_{1},x_{2},\dots ,x_{n})=0.

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