Karakteristlik aktsepteeriv TM on selline, mis aktsepteerib, kui x kuulub keelde. Muul juhul lükkab tagasi. Genereeriv aktsepteeriv TM on selline, mis aktsepteerib, kui x kuulub keelde. Muul juhul ei peatu. DEF: Hulka (keelt), millel leidub karakteristlik Turingi masin, nimetatakse lahenduvaks ehk rekursiivseks. DEF: Hulka (keelt), millel leidub genereeriv Turingi masin, nimetatakse rekursiivselt loenduvaks ehk genereeritavaks. Lemma: Iga lahenduv hulk on rekursiivselt loenduv. T: Igal lahenduva hulga karakteristlikku masinat saab 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)
Lõppolekus lõpetamine A(x) r, vastasel juhul A(x) = lõpmatus Karakteristlik Turingi masin: Turingi masinat A = (At,q,p,q0,Qf), kus Qf = (qt,qf) nimetatakse karakteristlikuks, kui see iga hulka X elemendi korral lõpetab töö qt-s, sellesse mittekuuluva korral qf-s. Lahenduv hulk millele saab leida Turingi masina. Turingi masina määramispiirkond M(A = {x | A(x) < lõpmatusest}) Hulk, mis on Turingi masina määramispiirkonnaks, nimetatakse genereeritavaks hulgaks. Iga lahenduv hulk on genereeritav: Teeme sellise masina, milles qf ei ole lõppolek seega läheb ta lõpmatusse tsüklisse iga mitte hulka kuuluva elemendi korral. 23. Turingi masina kodeerimine. Algoritmiliselt mittelahenduvad ülesanded. Church-Turingi tees. Turingi masina käsk: qiajqkX jooksev olek, järgmine sümbol, uus olek, tegevus (süboli kirjutamine + nihe L/R). Üleminekufunktsioon on esitatav käskude jadana. Käsud on eraldatud mingi separatoriga (nt ";").
annaabi.ee 
