T: Elementaarfunksioonid Registermasinal: On =0 on CLR, s(x)=x+1 on INC, Inm= xm on R → R. Ja ka Sm+1, R ja μy on reg.masinal arvutatavad. Neist saab konstrueerida kõik rek. funktsioonid. Ja reg.masin ja TM lahendavad samu asju. Teoreem: Iga registermasinal realiseeritav funktsioon on (osaline) rekursiivne funktsioon. Seega: Osaliselt rekursiivsete funktsioonide hulk langeb kokku Turingi mõttes arvutatavate funktsioonide hulgaga. 19 Minimeerimisoperaator. Osaliselt rekursiivsed funktsioonid. DEF: Funktsioon f : Nn → N on saadud funktsioonist g : Nn+1 → N minimeerimisoperaatori μy abil, kui kõikide väärtuste x1,...,xn ∈ N korral kehtib seos f (x1,...,xn) = a) y, mis on vähim selline element, et g(x1,...,xn,y) = 0 ja iga z < y korral g(x ,...,xn,z) on määratud ja pole 0; b) pole määratud, vastasel juhul. Ehk y on esimene element, mille puhul g(x1,...,xn,y) = 0.
Predikaat f.-n, mille väärtuste piirkond on kahendväärtus.
Kui g on arvutatav f.-n ja h1..hm on n-kohalised arvutatavad f.-nid, siis on ka f =
Sm+1[g,h1,..,hm] arvutatav.
Tõestus: eksisteerib registermasina programm
Kui g on n-kohaline arvutatav f.-n ja h on n+2 kohaline arvutatav f.-n, siis f =
R[g,h] on n+1-kohaline arvutatav f.-n.
Tõestus: eksisteerib registermasina programm
Neist kahest järeldub, et kõik lihtrekursiivsed funktsioonid on arvutatavad.
25. Minimeerimisoperaator. Osaliselt rekursiivsed funktsioonid.
Ütleme, et n-kohaline f.n f on saadud n+1-kohalisest funktsioonist g
minimeerimisoperaatori y abil f = y[g] abil, kui kogu määramispiirkonnas
y, kus y on min element, et g(x1,..xn,y) = 0, kusjuures iga z
annaabi.ee 
