sioonidest s(n) = n+1 ja q(n) = n−⌊√n⌋2, kasutades liitmise, kompositsiooni- ja pööramisoperaatorit. DEF: Funktsioonile h vastavusse seatud naturaalarv Gh (tema Gödeli number) arvutatakse nii: 2, kui h=s (s(n)=n+1) 3, kui h=q (q(n)=n−⌊√n⌋2) 5Gf · 7Gg, kui h=f+g 11Gf · 13Gg, kui h=f◦g 17Gf, kui h=f -1 19Gf, kui h=ιf Turingi mõttes arvutatavad on vaid need ühekohalised funktsioonid, mille jaoks leidub Gödeli number. 23 Kleene' s-m-n teoreem. Ühe funktsiooni Gödeli numbrist teise f.-ni Gödeli numbri arvutamine. Teoreem: Leidub selline m+1-kohaline (m y-t ja a) arvutatav funktsioon Snm, et suvaliste a,y1,...,ym korral kehtiks T: esitame selle ühekohaliste esindajate kaudu, kus y = cm(y1,…,ym) ja z = cn(z1,…,zn) muutujad: Siis on arvutatavad: Olgu funktsioon R(x) konstrueeritud järgmiselt: Näeme, et kehtib võrdus φR(x)(y) = c(x,y).
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 Kõik ühekohalised osaliselt rekursiivsed f.-nid on saadavad algf.-nidest s(x) = x+1 ja g(x) = |x (floor(sqrt(x)))2| (ruutjääk), kasutades liitmise-, kompositsiooni- ja pööramisoperaatoreid. 30. Kleene' s-n-m-teoreem ja püsipunktiprintsiip. N-kohalise f.-ni Gödeli numbriks on tema ühekohalise esindaja Gödeli number. a ühekohaline f.-n, mille Gödeli number olgu a. g olgu f ühekohaline esindaja. Kehib seos: f = a(n) = cn g o Kuna f (x1,..,xn) = g(y1,..,ym,x1,..,xn) saab esitada = x1 .. xn g(y1,..,ym,x1,xn) Kleene'i s-n-m teoreem: Ühe funktsiooni Gödeli numbrist teise f.-ni Gödeli numbri arvutamine. Leidub selline m+1-kohaline arvutatav f
annaabi.ee 
