"abiregistrit" - 1 õppematerjal

Rekursiooni ja keerukusteooria eksami konspekt

programm ja vastupidi. T: Turingi masina jaoks leidub registermasina programm. Selleks paneme TM ja tema lindil oleva sisendi registritesse, kasutades olekute ja tähtede indekseid koodina 0|…|0 (konteksti 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 }