Teoreem: Kõik ühekohalised osalised rekursiivsed funktsioonid on genereeritavad elementaarfunkt- 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:
-nide klassi U pole lihtrekursiivne: Tõestus: lihtrekursiivsed f.-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
annaabi.ee 
