"q0aq1ar" - 1 õppematerjal

Rekursiooni ja keerukusteooria eksami konspekt

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; • K (R) = 0||…|0 = t + 4; • K (qj)=0||···|0=t+5+j, kui qj∈Σ;