581336 Laskennan teoria (syksy 2003) Harjoitus 4 (11.14.11.2003)
Luennoilla määriteltiin epähuomiossa moninauhaiset Turingin koneet niin, että nauhapäät eivät saa pysyä paikallaan. Tämä ei ole lopputuloksen kannalta oleellista, mutta poikkeaa kurssikirjasta ja johtaa joissain tehtävissä turhiin hankaluuksiin. Jatkossa voidaan olettaa, että moninauhaisen koneen tapauksessa on sallittua myös pitää nauhapäätä paikallaan.
1. Todista luennolla esitetty tulos
Lause: Jos B on rekursiivisesti lueteltava jaA≤mB, niin myösAon rekursiivisesti lueteltava. Lisäksi josB on rekursiivinen, myösAon.
2. Ovatko seuraavat Turingin koneita koskevat ongelmat ratkeavia:
(a) onko koneessa ainakin 5 tilaa
(b) hylkääkö kone ainakin 5 merkkijonoa Perustele.
3. Tarkastellaan ongelmaa, onkoL(M1) =L(M2)kun M1 jaM2 ovat Turingin koneita. Muotoile tämä ongelma aakkoston {0,1} kielenä. Osoita, että kieli ei ole rekursiivisesti lueteltava (ts.
ongelma ei ole osittain ratkeava). Voit pitää tunnettuna, että tyhjyysongelmaLeei ole rekursii- visesti lueteltava.
4. Turingin koneen M tila q ∈ Q on turha jos M ei millään syötteellä koskaan siirry tilaan q. Muotoile päätösongelma Onko koneenM tilaqturha sopivana kielenä ja osoita, että ongelma ei ole ratkeava. Voit pitää tunnettuna, että tyhjyysongelma ei ole ratkeava.
5. Määritellään mielivaltaisella Turingin koneellaM kieli
Lb(M) ={0n1x|syötteelläxkoneM tekee korkeintaannsiirtymää ja hyväksyy}.
Siis0n1x6∈Ljos jokox6∈L(M)taix∈L(M)mutta syötteenxhyväksyminen vie koneeltaM ylinlaskenta-askelta. Osoita, että millä tahansaM kieliLb(M)on rekursiivinen.
6. Tarkastallaan mallia, jossa Turingin koneessa on erillinen tulostusnauha. Kyseessä on muuten normaali deterministinen moninauhainen Turingin kone, mutta tulostusnauhan nauhapäätä ei koskaan saa siirtää vasemmalle eikä tulostusnauhalle kirjoitettuja ei-tyhjiä merkkejä muuttaa.
Tulostusnauhallinen Turingin koneM luettelee kielenA⊆Σ∗, jos se saadessaan syötteenä tyhjän merkkijonon kirjoittaa tulostusnauhalle jonon w1#w2#w3#. . . missä {w1, w2, w3, . . .} = A. SiisM saa luetella kielenAmerkkijonot missä tahansa järjestyksessä, ja sama alkio saa toistua.
Tyypillisesti tulostusjono on päättymätön ja koneM ei pysähdy.
Osoita, että kieliL ⊆Σ∗ on rekursiivisesti lueteltava jos ja vain jos jokin tulostusnauhallinen Turingin kone luettelee sen. Voit käyttää hyväksi edellisen tehtävän tulosta.
