581336 Laskennan teoria (kevät 2006) Harjoitus 4, ratkaisuja
1. (a) Ongelma Annettu Turingin koneetM1 ja M2 sekä merkkijonox; hyväksyykö sekä kone M1 että koneM2syötteenx formaalina kielenä:
{w1111w2111x∈ {0,1}∗|x∈L(Mw1)jax∈L(Mw2)}, toisin sanoen
{w1111w2111x∈ {0,1}∗| x∈L(Mw1)∩L(Mw2)}.
(b) Ongelma Annettu Turingin koneetM1jaM2; onko olemassa syötex, jonka sekäM1 että M2 hyväksyvät formaalina kielenä:
{w1111w2∈ {0,1}∗ | ∃x:x∈L(Mw1)jax∈L(Mw2)}, toisin sanoen
{w1111w2∈ {0,1}∗ | ∃x:x∈L(Mw1)∩L(Mw2)}, eli
{w1111w2∈ {0,1}∗ |L(Mw1)∩L(Mw2)6=∅}.
(c) Kieli
{u111w∈ {0,1}∗ |L(Mu)∩L(Mw) =∅ jaL(Mu)∪L(Mw) ={0,1}∗}
esittää ongelmaa Annettu kaksi Turingin konetta; ovatko niiden tunnistamat kielet tois- tensa komplementteja.
(d) Määritellään luentokalvojen s. 91 tapaan, että ohjelma hyväksyy syötteen, jos sen suori- tus päättyy normaalisti, ja hylkää jos suoritus päättyy virheeseen. Ohjelman suoritus ei välttämättä pääty ollenkaan; tällöin ohjelma ei tietenkään hyväksy syötettä.
Täytyy vielä sopia jokin tapa koodata (ohjelma, syöte) -parit merkkijonoiksi. Oletetaan, että ohjelmat (oikeammin niiden C-kieliset lähdekoodit) ja syötteet ovat (esim.) ASCII- merkistön merkkijonoja. Ohjelma ja syöte on pystyttävä erottamaan toisistaan kooda- tussa esityksessä. Tässä aiheuttaa ongelmia se, että lähdekoodissa ja syötteessä voi ol- la mitä tahansa ASCII-merkkejä ja niiden yhdistelmiä. Koodataan ohjelma sen vuok- si vaikkapa seuraavasti: kutakin lähdekoodin merkkiä a ∈ ASCII vastaa merkkijono qkz, missä k on merkin a ASCII-koodi. Esimerkiksi merkki # koodataan merkkijonok- si qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqz, siis q35z, ja merkkiä { vastaa merkkijono q123z. Koodattu ohjelma koostuu siis vain q- ja z-merkeistä, ja syöte voidaan erottaa siitä esim. !-merkillä.
Olkoon OH jokin ohjelma, joka hylkää kaikki syötteet ja määritellään luentojen sivujen 8889 tapaan kaikille w ∈ ASCII∗ ohjelma Ow: jos w on jonkin ohjelman O C-kielinen lähdekoodi koodattuna edellä esitetyllä tavalla, niinOw=O, muutenOw=OH. Määritel- lään vielä ohjelman O tunnistama kieliL(O)niiden ASCII-merkkijonojen joukoksi, jotka O hyväksyy.
Universaalikieli on nyt {w!x∈ASCII∗ |x∈L(Ow)}.
2. Oletetaan, että kielet A ja B ovat rekursiivisesti lueteltavia. Määritelmän mukaan kieli X on rekursiivisesti lueteltava jos ja vain jos on olemassa Turingin koneM, jollaX =L(M). Oletuksen perusteella meillä on siis Turingin koneetMA jaMB, joiden tunnistamat kielet ovat vastaavasti AjaB. Muodostetaan näitä hyödyntäen tunnistajakoneet kielilleA∪B jaA∩B.
Muodostetaan kaksinauhainen Turingin kone kielenA∪B tunnistamiseen, mikä osoittaa kielen rekursiivisesti lueteltavaksi:
• Aluksi kone kopioi syötteen kakkosnauhalle ja palauttaa nauhapäät alkuun.
• Seuraavaksi simuloidaan koneen MA toimintaa ykkösnauhalla ja koneen MB toimintaa kakkosnauhalla samaan tapaan kuin luennoilla (s. 9597).
• Jos ainakin toinen simuloiduista koneista hyväksyy syötteen, hyväksytään syöte.
• (Jos kumpikin kone pysähtyy ja hylkää syötteen, hylätään syöte.)
Seuraava kaksinauhainen kone puolestaan tunnistaa kielenA∩B, mikä riittää osoittamaan kielen rekursiivisesti lueteltavaksi:
• Aluksi kone kopioi syötteen kakkosnauhalle ja palauttaa molemmat nauhapäät alkuun.
• Seuraavaksi simuloidaan koneenMAtoimintaa ykkösnauhalla.
• Jos MA hylkää syötteen, hylätään syöte.
• Jos taas MA hyväksyy syötteen, tyhjennetään ykkösnauha, kopioidaan sille alkuperäinen syöte kakkosnauhalta ja palautetaan nauhapäät alkuun.
• Lopuksi simuloidaan koneenMBtoimintaa ykkösnauhalla ja vastataan simulaation mukai- sesti.
3. Oletetaan, että rekursiivisesti lueteltavat kieletL1, . . . , Lk ovat kaikki erillisiä (eliLi∩Lj=∅, kun i6=j ja ne yhdessä kattavat kaikki mahdolliset merkkijonot (eli L1∪L2∪ · · · ∪Lk = Σ∗. Osoitetaan nyt, että kaikki kieletLi ovat rekursiivisia.
Havaitaan, että kaikillaipäteeLi=S
j6=iLj. Tehtävässä 2 osoitettiin, että kahden rekursiivisesti lueteltavan kielen yhdiste on rekursiivisesti lueteltava kieli. Tästä saadaan suoraan induktiolla, että yhdiste äärellisen monesta rekursiivisesti lueteltavasta kielestä on rekursiivisesti lueteltava (jos n kielen yhdiste on rekursiivisesti lueteltava, niin tämän yhdisteen ja n+ 1:nnen kielen yhdiste on myös rekursiivisesti lueteltava). Nyt siis kieli Li ja muiden kielten yhdisteS
j6=iLj ovat rekursiivisesti lueteltavia ja toistensa komplementteja, joten luennoilla esitetyn tuloksen (s. 98100) mukaisestiLi on rekursiivinen.
4. (a) Olkoon M yksinauhainen deterministinen Turingin kone. Muodostetaan kaksinauhainen kone M0 joka tunnistaa kielen Lb(M) ja pysähtyy kaikilla syötteillä. Kielen Lb(M) re- kursiivisuus seuraa tästä määritelmän mukaan. Idea on käyttää koneen M0 kakkosnauhaa käskylaskurina.
KoneM0 toimii seuraavasti:
i. Kopioi kaikki ykkösnauhan alusta löytyvät 0-merkit kakkosnauhalle ja pyyhi ne yli ykkösnauhalta (eli kirjoita päälle #).
ii. Jos ykkösnauhalta ei löytynyt yhtään1-merkkiä, hylkää; syöte ei ollut muotoa 0n1x millään x.
iii. Muuten pyyhi vielä ykkösnauhalta pois1-merkki; palauta kakkosnauhapää osoittamaan edellistä merkkiä.
iv. Jos alkuperäinen syöte oli 0n1w, nyt ykkösnauhalla on w ja nauhapää osoittaa sen alkuun, kakkosnauhalla 0n ja nauhapää osoittaa sen loppuun.
v. Simuloi nyt koneenM laskentaa ykkösnauhalla. Aina kun koneM tekisi siirtymän, tee vastaava siirtymä ja lisäksi siirrä kakkosnauhapäätä vasemmalle, jos kakkosnauhalla oli 0. Jos kakkosnauhalla oli #, hylkää. Muuten hylkää tai hyväksy jos M hylkää tai hyväksyy.
Selvästi syötteellä 0n1xsimulaatiovaiheessa suoritetaan korkeintaan naskelta ennen kuin kakkosnauhalta loppuu 0-merkit, joten kone M0 pysähtyy kaikilla syötteillä. Lisäksi on selvää, ettäM0 hyväksyy jos ja vain josM hyväksyy korkeintaannaskelella.
(b) Oletetaan, ettäAon rekursiivisesti lueteltava; olkoonA=L(M). Voidaan olettaa, ettäM ei tee mitään siirtymiä hyväksyvistä tiloista.
2
KoneMhyväksyy syötteenx, jos ja vain jos on olemassa sellainen (äärellinen) määrä askelia n, ettäM syöttelläxpäätyynaskelessa hyväksyvään tilaan ja pysähtyy. Siisx∈A, jos ja vain jos0n1x∈Lb(M)jollakinn∈N.
Koska A6=∅, voidaan valita jokin kiinteäa0∈A. Määritellään nyt funktiof seuraavasti:
f(w) =
x josw= 0n1xjollainnjaw∈Lb(M) a0 muuten.
Jos x∈A, niin x=f(0m1x), kunm on vähintään syötteen xhyväksymiseen koneelta M kuluvien askelten lukumäärä. Josx6∈A, niin0n1xei kuulu kieleenLb(M)milläänn, joten millään wei pädex=f(w).
Koska Lb(M)on rekursiivinen, funktio f on selvästi laskettava ja totaalinen. Se voidaan siis valita tehtävässä halutuksi funktioksi.
3
