argumendi x korral, annab U(K(A)*K(x)) = K(A(x)). Universaalse Turingi masina määramispiirkond pole lahenduv hulk. Registermasin: lõpmatu RAM. Suvaline arv registreid Ri kasutusel. Iga sisuks on naturaalarv. Programm on operaatorite jada. Igal operaatoril Ni märgend. 7 liiki operaatoreid: INC DEC CLR JMP Rj = Ri JMP if NULL CONTINUE Iga Turingi masinal arvutatav f.-n on realiseeritav registermasinal. Tõestus kirjutame Turingi masina üleminekufunktsiooni registermasina mällu. Iga registermasina programm on realiseeritav Turingi masinal: Esitame registermasina kõigi nullist erinevate registrite sisu Turingi masina lindil Turingi masin ja registermasin on arvutatavuse mõttes ekvivalentsed. Church-Turingi tees: iga efektiivselt arvutatav funktsioon on realiseeritav Turingi masinal 24. Lihtrekursiivsed funktsioonid, nende arvutatavus Turingi mõttes. Arvtatavuseks piisab kolmest operaatorist: · superpositsioon (f.-nide järjest rakendamine) · rekursioon (f
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). Teoreem: Registermasina iga programmi jaoks leidub ekvivalentne (deterministliku) Turingi masina programm ja vastupidi
annaabi.ee 
