581336 Laskennan teoria (kevät 2006) Harjoitus 6, ratkaisuja
1. Ongelma on ratkeava.
Oletetaan, että koneessa M on m tilaa. Väitetään, että jos M syötteellä x siirtää ainakin ker- ran nauhapäätä vasemmalle, niin nauhapää siirtyy vasemmalle ainakin kerran jo jxj + m + 1 ensimmäisen laskenta-askelen aikana.
Oletetaan siis, että jxj + m + 1 ensimmäisen laskenta-askelen aikana nauhapää on koko ajan siirtynyt oikealle. Tällöin se on siis ensinnäkin ohittanut koko syötteen x ja lisäksi m + 1 tyhjä- merkkiä syötteen jälkeen. Tästä seuraa, että ainakin yhdessä m tilasta on tyhjäosuuden aikana käyty ainakin kaksi kertaa. Tästä seuraa, että M on ikuisessa silmukassa, ja lukee jatkuvas- ti tyhjämerkkejä siirtäen nauhapäätä oikealle ja palaten säännöllisin väliajoin tähän samaan tilaan.
Ongelma voidaan siis ratkaista simuloimalla koneen M laskentaa syötteellä x tasan jxj + m + 1 askelta. Jos nauhapää siirtyy ainakin kerran vasemmalle, vastaus on kyllä, muuten ei.
2. (a) Muotoillaan ongelma formaalina kielenä A =
w 2 f 0; 1 gj jL(Mw)j 3 :
Nyt A on muotoa A = LS, missä S on ei-triviaali semanttinen ominaisuus S = f L(M) j jL(M)j 3 g :
Ricen lauseen nojalla S on ratkeamaton eli A ei ole rekursiivinen.
Kieli A on rekursiivisesti lueteltava. Se voidaan tunnistaa esim. seuraavanlaisella kaksinau- haisella epädeterministisellä Turingin koneella:
i. Arvaa epädeterministisesti merkkijono #x1#x2#x3 ja kirjoita syötteen jatkoksi yk- kösnauhalle.
ii. Ykkösnauhalla on nyt w#x1#x2#x3. Jos x1= x2tai x1= x3tai x2= x3 niin hylkää.
iii. Toista seuraavaa arvoilla i = 1; 2; 3:
A. Kirjoita kakkosnauhalle merkkijono w111xi.
B. Simuloi universaalikoneen laskentaa kakkosnauhalla. Jos universaalikone hylkäisi, niin hylkää. Jos universaalikone hyväksyisi, niin siirry seuraavaan iteraatioon.
iv. (Jos tänne päästään, niin kaikki kolme simulaatiota ovat hyväksyneet.) Hyväksy.
(b) Muotoillaan ongelma formaalina kielenä
B = f u111v j jL(Mu) \ L(Mv)j 3 g :
Olkoon v0 jokin koodi Turingin koneelle Mall, joka hyväksyy kaikki syötteet. Siis L(Mv0) = f 0; 1 g, ja erityisesti L(M) \ L(Mv0) = L(M) kaikilla M. Määritellään funktio f : f 0; 1 g! f 0; 1 g, f(w) = w111v0. Selvästi f on rekursiivinen. Lisäksi
w 2 A , jL(Mw)j 3
, jL(Mw) \ L(Mv0)j 3 , f(w) 2 B:
Siis f on rekursiivinen palautus A mB. Koska A ei ole rekursiivinen, myöskään B ei ole.
Huomautus: Tarkastetaan vielä varmuuden vuoksi tapaus, jossa w ei ole validi koodi. Siis määritelmän mukaan w 62 A. Toisaalta tällöin merkkijonoa f(w) = w111v0 ei mitenkään voida esittää muodossa w111v0 = u111v missä jL(Mu) \ L(Mv)j 3. (Tämä nimittäin edellyttäisi vähintään, että L(Mu) ja L(Mv) olisivat epätyhjiä ja siis sekä u että v valideja koodeja.) Siis f(w) 62 B, niin kuin pitääkin
3. Tarkennus tehtävään: tarkoitetun minimointialgoritmin pitäisi palauttaa syötteellä M sellai- nen mahdollisimman vähän tiloja sisältävä M0, jolla L(M0) = L(M) ja jolla on sama nauha- aakkosto kuin koneella M.
Tällaista minimointialgoritmia ei ole olemassa.
Todistuksen perusidea voidaan esittää (hieman virheellisesti) seuraavaan tapaan: Tehdään vas- taoletus, että Minimoi olisi tällainen algoritmi. Olkoon lisäksi M0 pienin sellainen Turingin ko- ne, jolla L(M0) = ;. Nyt seuraava proseduuri Tyhjä(M) ratkaisee tyhjyysongelman eli päättää, päteekö L(M) = ;:
(a) Laske M0 = Minimoi(M).
(b) Jos M0= M0 niin hyväksy, muuten hylkää.
Tämä on kuitenkin mahdotonta, koska tyhjyysongelma on ratkeamaton. Siis proseduuria Mini- moi ei ole olemassa.
Edellisessä todistusideassa on se vika, että M0 ei ole yksikäsitteinen: on olemassa monta saman kokoista pienintä Turingin konetta, jotka eivät hyväksy yhtään merkkijonoa. Tarkennamme siis todistusta seuraavasti:
Valitaan ensin sellainen m, että tyhjyysongelma on ratkeamaton, vaikka se rajoitettaisiin konei- siin, joiden nauha-aakkoston koko on korkeintaan m. Siis vaaditaan, että kieli
L(m)e = f w j koneen Mw nauha-aakkoston koko on kork. m ja L(Mw) = ; g on ei-rekursiivinen.
Tarkastelemalla tyhjyysongelman ratkeamattomuustodistusta (joka perustuu epätyhjyysongel- man ratkeamattomuuteen, luentojen sivut 125128) nähdään, että siinä konstruoitavien Turin- gin koneiden Mwnauha-aakkosto on sama kuin universaalikoneen nauha-aakkosto. Todistuksesta siis seuraa suoraan kielen L(m)e ei-rekursiivisuus, kun m on vähintään (jonkin) universaalikoneen nauha-aakkoston koko.
Olkoon nyt k pienin sellainen luonnollinen luku, että L(M) = ; jollain k-tilaisella Turingin koneella M, jonka nauha-aakkoston koko on korkeintaan m.
Olkoon f M1; : : : ; Mng niiden k-tilaisten, koneen M kanssa saman nauha-aakkoston omaavien Turingin koneiden M joukko, joilla L(M) = ;. Huomaa, että tämä joukko on äärellinen, koska k-tilaisia kiinteää nauha-aakkostoa käyttäviä Turingin koneita on vain äärellinen määrä.
Tehdään taas vastaoletus, että proseduuri Minimoi(M) palauttaa tilamäärältään pienimmän Turingin koneen, joka hyväksyy saman kielen kuin M ja käyttää samaa nauha-aakkostoa. Nyt saamme (nauha-aakkoston kokoon m rajoitetulle) tyhjyysongelmalle modioidun algoritmin
(a) Laske M0 = Minimoi(M).
(b) Jos M02 f M1; : : : ; Mng niin hyväksy, muuten hylkää.
Kuten aiemmin, sanotaan että ohjelma p hyväksyy syötteen x, jos syötteellä x ohjelman p suo- ritus päättyy normaalisti. Vaihtoehdot ovat, että suoritus päättyy virheeseen, jolloin sanomme että ohjelma hylkäsi syötteen x, tai että ohjelma jää ikuiseen silmukkaan. Mitataan C-ohjelman pituutta sen (lähdekoodin) merkkien lukumäärällä, kun rivinvaihto lasketaan yhdeksi merkiksi.
Ylläoleva tulos C-ohjelmille sovellettuna sanoo, että ei ole olemassa algoritmia, joka saisi syöt- teenä mielivaltaisen C-ohjelman koodin ja palauttaisi lyhimmän ohjelman, joka hyväksyy saman kielen. Tulos voidaan todistaa C-kielelle aivan samoin kuin edellä käyttäen hyväksi tietoa, että myös C-kielen tyhjyysongelma on ratkeamaton.
4. Tämä on samansukuinen tehtävä kuin edellisen kerran tehtävä 2. Määritellään syötteen hyväk- syminen kuten edellisessä tehtävässä.
2
Tehdään vastaoletus, että proseduuri Turvallinen(p) palauttaa tosi, jos ohjelma p ei millään syötteellä yritä jakaa nollalla, ja muuten epätosi. Katsotaan, saadaanko tästä ristiriita löytä- mällä algoritmi jollekin tunnetulle ratkeamattomalle ongelmalle. Hyviä kandidaatteja tällaiseksi ongelmaksi ovat ohjelmointikieleen liittyvät semanttiset ongelmat (luentojen s. 139). Näissä on pohjimmiltaan kysymys siitä, mitä syötteitä hyväksytään.
Haluamme siis muuntaa kysymyksen syötteen hyväksymisestä kysymykseksi nollalla jakamises- ta. Lähdetään liikkeelle tekemällä ohjelmaan muunnos, jossa kirjamellisesti hyväksymiset kor- vataan nollalla jakamisella. Otetaan samalla ylimääräiset nollalla jakamiset pois. Annetusta ohjelmasta p siis tehdään muunnettu ohjelma p0 seuraavasti:
(a) Kaikki ohjelman p normaalit päättymistavat korvataan ohjelmassa p0 nollalla jakamisella.
(b) Jos p sisältää jakolaskuja, liitä ohjelmassa p0niihin eksplisiittinen tarkistus, ettei jakaja ole nolla. Jos jakaja olisi nolla, ohjelma p0 ei suorita jakolaskua vaan pysähtyy normaalisti.
(c) Muuten p0 on kuin p.
Katsotaan nyt, mitä tarkalleen saatiin aikaiseksi. Tarkastellaan ensin jotakin yksittäistä x.
(a) Jos p hyväksyy syötteen x, niin erityisesti p ei syötteellä x yritä suorittaa nollalla jakoa.
Siis ohjelmien p ja p0 toiminta ei eroa, ennen kuin p pysähtyy. Tällöin p0 jakaa nollalla.
(b) Jos p hylkää, koska tapahtui nollallajakamisvirhe, niin p0 toimii tähän nollallajakokohtaan asti kuten p ja pysähtyy. Erityisesti p0 ei jaa nollalla.
(c) Jos p hylkää muun virheen takia kuin nollalla jakamisen, tai jos p jää ikuiseen silmukkaan, niin p0 käyttäytyy aivan kuin p. Erityisesti p0 ei jaa nollalla.
Siis annetulla syötteellä x ohjelma p hyväksyy, jos ja vain jos ohjelma p0 jakaa nollalla.
Palautetaan nyt mieliin vastaoletuksena oleva proseduuri Turvallinen, joka tutkii tapahtuuko nollalla jakamista millään syötteellä. Siis
Turvallinen(p0) = tosi , p0 ei millään syötteellä jaa nollalla , p ei millään syötteellä hyväksy:
Havaitsemme, että olemme saaneet algoritmin Tyhjä(p) tyhjyysongelmalle onko ohjelman p hyväksymien syötteiden joukko tyhjä:
Tyhjä(p):
(a) Muodosta p0 ylläesitetyllä konstruktiolla.
(b) Jos Turvallinen(p0) niin hyväksy, muuten hylkää.
Koska muunnos p 7! p0 on selvästi laskettava, edellä esitettyjen havaintojen perusteella tämä ratkaisee tyhjyysongelman, joka kuitenkin tiedetään ratkeamattomaksi; ristiriita.
3
