järgi saame hiljem aru, kas on olek v täht). t+1 on L ja t+2 on R. Kirjutame TM üleminekufunktsioonid koodina tabelisse. Nüüd kirjutame tabeli registermällu (igale lahtrile 1 register) ja lisame 7 abiregistrit: hetkeolek, lugemispea asukoht, loetud täht, kirjutatud täht/L/R, vahetulemused, tähtede arv t. Registermasin lõpetab töö, kui TM jõuab lõppolekusse. Registrites Rx… on y=TM(x) kood. 17 Turingi masina kodeerimine. Algoritmiliselt mittelahenduvad ülesanded. Church-Turingi tees. Turingi masinat saab esitada ka programmina: kirjutada järjest hetkeolek, sisend ja jrg olek: q0aq1aR Olgu Turingi masina programm P = x1…xn ning Turingi masina lindi tähestik Σ={ a0,..,at }. Turingi masina kood tähestikus Σ={ 0,| } on sõne K = K(x1)K(x2)...K(xn), kus • K (ai)=0||···|0=i, kui ai∈Σ; (i = 0…t) • K (;) = 0||…|0 = t + 1; (tähestiku viimane on t) • K (L) = 0||…|0 = t + 2; • K (S) = 0||…|0 = t + 3;
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 ";"). Programm on siis sümbolite jada P = x1x2...xn. Turingi masina kood on sõna K(P) tähestikus A = {_,|,0}, kus K(P) = K(x1)K(x2)..K(xn). K(ai) = 0|| ..i tk.. ||0 i kuulub At K(;) = 0|| .. t+1 tk.. ||0 K(L) = 0|| ..t+2
annaabi.ee 
