Rekurzivne funkcije

Skoči na: navigacija, iskanje

Splošno rekurzivne funkcije

to so funkcije oblike:

$\mathbb{N}^k \rightarrow \mathbb{N}$

Ničelna funkcija:
$\forall x:\ Z(x)=0$
Funkcija naslednika:
$\forall x:\ N(x)=x+1$
Projekcija:
$\forall n,\ \forall i, 1 \le i \le n: U_i^n(x_1,x_2,...,x_n)=x_i$
Funkcijska kompozicija:
$h_i(x_1,x_2,...,x_n)\ \in\ SFR$
$g(x_1,x_2,...,x_m)\ \in\ SFR$
$f(x_1,x_2,...,x_n)=g(h_1(x_1,x_2,...,x_n),h_2(x_1,x_2,...,x_n),...,h_m(x_1,x_2,...,x_n))\ \in\ SFR$
Primitivna rekurzija:
$f(x_1,x_2,...,x_n,y)\ \in\ SFR$
$f(x_1,x_2,...,x_n,0)=g(x_1,x_2,...,x_n)\ \in\ SFR$
$f(x_1,x_2,...,x_n,y+1)=h(x_1,x_2,...,x_n,y,f(x_1,x_2,...,x_n,y))\ \in\ SFR$
Minimizacija:
$g(x_1,x_2,...,x_n,y)\ \in\ SFR$
$f(x_1,x_2,...,x_n)=\mu_y \left [g(x_1,x_2,...,x_n,y)\right ]$ Minimalna vrednost y, pri kateri je g()=0, drugače je f nedefiniran