Rekursiooni ja keerukusteooria eksami konspekt
tesendada nii, et ta jääks olekusse qr jõudmise asemel tsüklisse ehk muutuks genereerivaks masinaks.
Registermasin sisaldab registreid R1… (sisuks naturaalarv) ja märgendeid N1… Operaatorid on INC (+1),
DEC (-1), CLR (nullimine), R → R (omastad ühe väärtuse teisele), JMP Na (go to N), JMP Nb (go to N+1),
R JMP Na (kui R=0…), R JMP Nb, CONTINUE (ei tee midagi). Registermälu kasutab suvapöördusmälu
RAM ehk on võimeline iga oma registrini pöörduma võrdse ajaga. Mälu ja registri suurus on piiramatud.
DEF: Registermasina programm P realiseerib funktsiooni f (x1…xn ) parajasti siis, kui ta käivitatuna seisus,
kus registrid R1,...,Rn sisaldavad arve x1,...,xn ning teised programmi P kasutatavad registrid on
algväärtustatud 0-dega, peatub ainult juhul, kui f(x1,...,xn) on määratud, kusjuures peatamise korral on
registris R1 arv f(x1,...,xn).
annaabi.ee 
