581336 Laskennan teoria (kevät 2006) Harjoitus 3 (7.-10.2.)
1. Esitä rajoittamaton kielioppi, joka tuottaa kielen
f aibjck j i > 0; j > 0; k = i + j g:
2. (a) Konstruoi rajoittamaton kielioppi, joka tuottaa kielen f 0n1n j n 1 g, soveltamalla luen- nolla (sivulta 67 alkaen) esitettyä menettelyä luennolla (sivulla 31) esitettyyn Turingin koneeseen.
(b) Esitä konstruoimassasi kieliopissa johto merkkijonolle 01.
3. (a) Mikä merkkijono on luennoilla esitetyn numeroinnin mukaan w21?
(b) Esitä jokin koodi luennoilla (s. 31) esitetylle kielen f 0n1n j n 1 g hyväksyvälle Turingin koneelle.
4. Todista oheiset laskettavia funktioita ja ratkeavia ongelmia yhdistävät tulokset. Vaikka tulokset on tässä muotoiltu Turingin koneiden avulla, älä kiinnitä ratkaisussasi liikaa huomiota Turingin kone -formalismiin, vaan keskity siihen, miten yleisemmin funktion f laskevasta algoritmista voidaan muodostaa päätösongelman A ratkaiseva algoritmi jne.
(a) Jos f: ! on totaalinen Turingin koneella laskettavissa oleva funktio ja A = f f(w) j w 2 g, niin kieli A on rekursiivisesti lueteltava.
(b) Jos f: ! on totaalinen ja monotoninen Turingin koneella laskettavissa oleva funktio ja A = f f(w) j w 2 g, niin kieli A on rekursiivinen. (Funktion f monotonisuus tarkoittaa tässä, että jos w on leksikograsessa järjestyksessä ennen kuin v, niin myös f(w) on ennen kuin f(v).)
(c) Jos A on rekursiivinen, niin on olemassa totaalinen ja monotoninen Turingin koneella las- kettavissa oleva funktio f, jolla A = f f(w) j w 2 g. (Vihje: tämä f on yksikäsitteinen.) (Pitää myös paikkansa, että jos A on rekursiivisesti lueteltava, niin on olemassa totaalinen Turin- gin koneella laskettavissa oleva funktio f, jolla A = f f(w) j w 2 g; sivuutamme todistuksen toistaiseksi.)
