"qiajqkx" - 1 õppematerjal

Teoreetilibe informaatika kordamisküsimused

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.. ||0 K(R) = 0|| .. t+3.. ||0 K(qi) = 0|| ..t+4+i.