581336 Laskennan teoria (kevät 2006) Harjoitus 6 (14.-17.3.)
Tenttiviikolla 27.2.-3.3 ja väliviikolla 6.-10.3. ei ole luentoja eikä laskuharjoituksia.
1. Osoita, että ongelma Siirtääkö annettu Turingin kone annetulla syötteellä koskaan nauhapää- tään vasemmalle on ratkeava.
2. (a) Tarkastellaan ongelmaa
Annettu: Turingin kone M
Kysymys: hyväksyykö M vähintään kolme eri merkkijonoa
Onko ongelma ratkeava? Entä osittain ratkeava? (Vihje: epädeterminismi.) (b) Tarkastellaan ongelmaa
Annettu: Turingin koneet M1 ja M2
Kysymys: onko jL(M1) \ L(M2)j 3
Osoita, että ongelma on ratkeamaton. (Vihje: palautus (a)-kohdan ongelmasta.) Kummassakin kohdassa muotoile ongelma formaaliksi kieleksi ja perustele huolellisesti.
3. Onko Turingin koneille olemassa minimointialgoritmi, ts. algoritmi, joka syötteellä M palauttaa mahdollisimman vähän tiloja sisältävän koneen M0, jolle L(M) = L(M0)? Perustele.
Muotoile vastaava tulos C-kielisille ohjelmille.
4. Olisi ilmeisen hyödyllistä, jos ohjelmasta voitaisiin jo käännösvaiheessa todeta, johtaako se jollain syötteellä nollalla jakamiseen. Perustele, miksi tällaista tarkastusta ei voi tehdä niin, että se aina varmasti toimisi.
