KV-keelte ühesuse probleem pole algoritmiliselt lahenduv Church-Turingi tees: Iga efektiivselt (algoritmiliselt) arvutatav funktsioon on realiseeritav (arvutatav) Turingi masinal. Ehk iga asja, mida saab normaalse aja jooksul välja arvutada, saab arvutada ka Turingi masinal. 18 Lihtrekursiivsed funktsioonid, nende arvutatavus Turingi mõttes. DEF: Lihtrekursiivsed funktsioonid on konstrueeritavad elementaarfunktsioonidest superpositsiooni- ja rekursioonioperaatori abil. Lihtrekursiivsed funktsioonid on kõikjal määratud. nt summa, korrutis, x!, sign Elementaarfunktsioonideks loetakse järgmised funktsioonid: • konstantne funktsioon On : Nn → N, mis iga väärtuste komplekti x1,...,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,.
-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 
