581336 Laskennan teoria (kevät 2006) Harjoitus 4 (14.-17.2.)
1. Laskennalliset ongelmat esitetään usein tyyliin Annettu: Turingin kone M, merkkijono x Kysymys: Hyväksyykö kone M syötteen x
Jotta tällaisesta ongelmasta voidaan puhua tämän kurssin käsitteillä, se pitää esittää formaalina kielenä. Ylläolevan esimerkkiongelman esitys formaalina kielenä on luennolla esitetty universaa- likieli Lu.
(a) Määrittele samaan tapaan formaalina kielenä ongelma Annettu: Turingin koneet M1 ja M2, merkkijono x
Kysymys: Hyväksyykö sekä kone M1 että kone M2 syötteen x.
(b) Sama ongelmalle
Annettu: Turingin koneet M1 ja M2
Kysymys: Onko olemassa syöte x, jonka sekä M1 että M2 hyväksyvät.
(c) Tulkitse, mitä laskennallista ongelmaa esittää kieli
f u111w 2 f 0; 1 gj L(Mu) \ L(Mw) = ; ja L(Mu) [ L(Mw) = f 0; 1 gg:
(d) Miten määrittelisit universaalikielen, jos haluttaisiin puhua Turingin koneiden sijaan C- kielisistä ohjelmista? (Sinun pitää määritellä, mitä tarkoitat hyväksymisellä C-ohjelman tapauksessa, ja koodata (ohjelma, syöte) -parit merkkijonoiksi.)
2. Osoita, että jos A ja B ovat rekursiivisesti lueteltavia, niin myös A [ B ja A \ B ovat.
3. Olkoon L1; : : : ; Lk sellainen kokoelma aakkoston kieliä, että (a) Li\ Lj = ; kun i 6= j,
(b) L1[ L2[ : : : [ Lk= ja
(c) jokainen kieli Li on rekursiivisesti lueteltava.
Osoita, että jokainen kieli Li on rekursiivinen.
4. Määritellään mielivaltaisella Turingin koneella M kieli
Lb(M) = f 0n1x j syötteellä x kone M tekee korkeintaan n siirtymää ja hyväksyy g:
Siis 0n1x 62 L, jos joko x 62 L(M) tai x 2 L(M) mutta syötteen x hyväksyminen vie koneelta M yli n laskenta-askelta.
(a) Osoita, että millä tahansa M kieli Lb(M) on rekursiivinen. (Vihje: Oletetaan, että M on yksinauhainen. Simuloi konetta M kaksinauhaisella koneella käyttäen kakkosnauhaa siirtymien laskemiseen.)
(b) Osoita, että jos A f 0; 1 g on rekursiivisesti lueteltava ja A 6= ;, niin on olemassa totaalinen Turingin koneella laskettava funktio f, jolla A = f f(w) j w 2 f 0; 1 gg. (Vihje:
tarkastele funktioita f, joilla f(0n1x) = x tietyillä n ja x.)
