|
|
Rekurzivne funkcije
Rekurzivne funkcije predstavljaju jednu klasu aritmetičkih funkcija.Definicijom rekurivnih funkcija precizira se intuitivni pojam algoritma i to tako da je ova definicija ekvivalentna drugim pristupima strogom definisanju pojma algoritma. Čerčova teza:“Skup rekurzivnih funkcija jednak je skupu intuitivno izračunljivih funkcija”.
Funkcije odredjene jednakostima:
f(x)=0 (nula funkcija)
f(x)=x+1 (naslednik funkcija)
(x1,x2,...,xj)=xi (projekcijska funkcija) , (i,j=1,2,3,....:i <_ (manje i jednako)j)
Neka su f,g,h funkcije za koje važe jednakosti
f(x1,x2,...,xn,0)=g(x1,x2,...,xn)
f(x1,x2,...,xn, y+1)=h(x1,x2,...,xn,y,f(x1,x2,...,xn,y))
za sve prirodne brojeve x1,x2,...,xn,y. Kažemo da se funkcija f dobija pomoću funkcija g i h rekurzijom.Za x1,x2,...,xn kažemo da su parametri rekurzije.
Ako nema parametar rekurzije onda jednakosti glase:
f(0)=k
(y+1)=h(y,f(y)) gde je k neki prirodan broj
Neka je g funkcija koja ima sledeće svojstvo:
('za svako'x1)('za svako'x2)...('za svako'xn)('postoji'y)(g(x1,x2,...,xn,y)=0)
Neka μy(g(x1,x2,...,xn,y)=0)
označava za date brojeve x1,x2,...,xn, najmanji broj y za koji je f(x1,x2,...,xn,y)=0
Kada jednakost f(x1,x2,...,xn)= μy(g(x1,x2,...,xn,y)=0)
jedinstveno odredjuje funkciju f. Kažemo da je funkcija f dobijena od funkcije g pomoću μ-operatora.
Neka su date funkcije g,h1,h2,...,hk.
Tada jednakost f(x1,x2,...,xn)=g(h1(x1,x2,...,xn),h2(x1,x2,...,xn),...,hk(x1,x2,...,xn)) jedinstveno odredjuje funkciju f. Kažemo da je funkcija f odredjena supstitucijom pomoću funkcija g,h1,h2,...,hk.
Definicija 1.
Za funkciju f: N' → N, gde je k neki poyitivan prirodan broj, kažemo da je rekurzivna ako postoji bar jedan konačan niz funkcija f1,f2,...,fn(fn je jednaka sa f) tako da svaka funkcija f toga niza zadovoljava uslov:
• fi je polazna funkcija, ili
• fi se odredjuje pomoću nekih prethodnih članova niza rekurzijom, supstitucijom ili μ -operatotam