..,xn ∈ N korral omab väärtust 0. • järgmise naturaalarvu funktsioon s : N → N, mis iga x ∈ N korral annab väärtuse s(x)=x+1; • projektsioonifunktsioon Inm : Nn → N, kus m <= n, mis iga väärtuste komplekti x1,...,xn ∈ N korral omab väärtust Inm(x1,...,xn) = xm. (valib n-st m-nda) DEF: (funktsioonide järjest rakendamine, liitfunktsioon) Funktsioon f on saadud funktsioonist g ja funktsioonidest h1,…,hm superpositsioonioperaatori Sm+1 abil, kui kõikide väärtuste x1,...,xn ∈ N korral kehtib seos f (x1,...,xn) = g(h1(x1,...,xn),...,hm(x1,...,xn)). Funktsiooni f esitatakse sel juhil operaatortermi abil järgmiselt: f = Sm+1[ g, h1,…, hm] (h-sid m tk + g = m+1 funktsiooni) DEF: (funktsiooni väärtust kasutatakse iseenda argumendina) Funktsioon f on saadud funktsioonist g ja funktsioonidest h rekursioonioperaatori R abil, kui kõikide väärtuste x1,...,xn ∈ N ja y ∈ N korral kehtivad
masinal
24. Lihtrekursiivsed funktsioonid, nende arvutatavus Turingi mõttes.
Arvtatavuseks piisab kolmest operaatorist:
· superpositsioon (f.-nide järjest rakendamine)
· rekursioon (f.-ni rakendamine iseenda sees omaenese eelmistele
väärtustele)
· minimeerimine arvutamine teatud tingimuse täitumiseni
Superpositsioon:
n-kohaline f.-n f on saadud m kohalisest f.-nist g ja n kohalistest f.-nidest hi (i =
1,..,m) superpositsioonioperaatori rakendamisel, kui
f = Sm+1(g;h1,..,hm) = g(h1,..,hm)
Rekursioon:
n+1-kohaline f-n f on saadud n-kohalisest f.-nist g ning n+2-kohalisest f.-nist h
rekursioonioperaatori rakendamisel, kui iga xi ja y korral kehtivad võrdused:
f = R[g,h]:
f(x1,..,xn,0) = g(x1,..,xn)
f(x1,..,xn,y+1) = h(x1,..xn,y,f(x1,..,xn,y))
Algfunktsioonid:
On(x1,..,xn) = 0 (n-kohaline konstant)
s(x) = x+1
Inm (x1,..,xn) = xm (0
annaabi.ee 
