Prakikumid ja kodutööd
Kool: Tartu Ülikool (TÜ)
Aine: Teoreetiline informaatika
Kategooria: Informaatika
Postitatud: 7 jaanuar 2025
Postitaja: HellGorilla
Kirjeldus
Teoreetiline informaatika Kevad 2024 8. kodutöö lahendused 1. Selles ülesandes deneerime kaks uut Turingi masinate tüüpi tüüp A ja tüüp B. Need uued masinad on sarnased tavaliste Turingi masinatega järgmiste erinevustega. (a) Tüüpi A masina pea võib ühe sammuga liikuda kuni kolme koha võrra vasakule või kuni kolme koha võrra paremale. Formaalselt on seda tüüpi masin deneeritud kui seitsmik (Q Σ Γ δ q0 qakts qtag) nagu tavaline Turingi masin. Üleminekufunktsioon δ on deneeritud järgmiselt δ Q Γ Q Γ 3L 2L L R 2R 3R. kus sL tähendab pea liikumist s koha võrra vasakule ning sR tähendab pea liikumist s koha võrra paremale. Tõesta et tüüpi A Turingi masinate klass on ekvivalentne tavaliste Tu- ringi masinate klassiga. (b) (Boonus 10 p) Tüüpi B masina pea saab liikuda ainult ühe ko- ha võrra paremale. Seda tüüpi masin on samuti deneeritud kui seitsmik (Q Σ Γ δ q0 qakts qtag). Üleminekufunktsioon δ on deneeritud järgmiselt δ Q Γ Q Γ R. Tõesta et tüüpi B Turingi masinate poolt aktsepte…