• 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 seosed f(x1,…,xn,0) = g(x1,...,xn) ja f(x1,...,xn,y+1) = h( x1,…,xn, y, f(x1,…,xn,y) ). f =R[g,h] Teoreem: Rekursiivsed funktsioonid on Turingi masinal arvutatavad. T: Elementaarfunksioonid
-nid on kõikjal määratud nende hulgas leidub s(x) = x+1, millle korral f.-nil pole püsipunkti Osaliselt rekursiivsete f.-nide klassi U on osaliselt rekursiivne 29. Ühekohaliste funktsioonide arvutatavus. Gödeli numbrid. Gödeli number: f.-ni h Gödeli number arvutatakse: 2, kui h = s 3, kui h = q G(h) = 5Gf * 7Gg, kui h = f + g 11Gf * 13Gg, kui h = f * g 17Gf, kui h = f-1 19Gf, kui h = if Gödeli f.-n kodeerib f.-ni tuletusele vastava operaatortermi. N-kohalise f.-ni Gödeli numbriks on tema ühekohalise esindaja Gödeli number. Ühele f.-nile võib leida mitu Gödeli numbrit (kuna tuletusi algf.-nidest võib olla mitu), üks Gödeli number vastab alati kindlale f.-nile. Arvutatavus: Robinsoni teoreemid: I Kõik ühekohalised lihtrekursiivsed f.-ni on arvutatavad algf.-nidest s(x) = x+1 ja g(x) = |x (floor(sqrt(x)))2| (ruutjääk), kasutades liitmise, kompositsiooni- ja iteratsioonioperaatoreid II
annaabi.ee 
