581336 Laskennan teoria (kevät 2006) Harjoitus 5 (21.-24.2.)
1. Tarkastellaan tilassakäyntiongelmaa
Annettu: Turingin kone M, merkkijono x
Kysymys: kun Turingin kone M suorittaa laskennan syötteellä x, niin siirtyykö se koskaan tilaan numero 5
Jos sinulla olisi algoritmi tämän ongelman ratkaisemiseksi, miten voisit ratkaista pysähtymison- gelman? Päättele, että tilassakäyntiongelma on ratkeamaton.
2. Tarkastellaan ongelmaa, onko L(M1) = L(M2) kun M1 ja M2 ovat Turingin koneita. Muotoile tämä ongelma aakkoston f 0; 1 g kielenä. Osoita, että kieli ei ole rekursiivisesti lueteltava (ts.
ongelma ei ole osittain ratkeava). Vihje: tee rekursiivinen palautus tyhjyysongelmasta Le. 3. Tarkastellaan ongelmaa
Annettu: Turingin kone M
Kysymys: hyväksyykö M merkkijonon 000
(a) Muotoile ongelma formaalina kielenä ja osoita Ricen lauseen avulla, että se on ratkeamaton.
Perustele yksityiskohtaisesti, miksi lause soveltuu tähän tilanteeseen.
(b) Osoita ongelma osittain ratkeavaksi palauttamalla se universaalikieleen Lu.
4. Olkoon L f 0; 1 g jokin rekursiivisesti lueteltava kieli, jolla L ei ole rekursiivisesti lueteltava.
Muodostetaan kieli
B = f x0 j x 2 L g [ f x1 j x 62 L g:
Mitä voidaan päätellä kielen B rekursiivisuudesta tai rekursiivisesta lueteltavuudesta? Entä kielelle B? Perustele. (Vihje: mitä kieliä osaat rekursiivisesti palauttaa kieleen B?)
