581336 Laskennan teoria (kevät 2006) Harjoitus 5, ratkaisuja

581336 Laskennan teoria (kevät 2006) Harjoitus 5, ratkaisuja

1. Tilassakäyntiongelma on ratkeamaton, sillä pysähtymisongelma voidaan palauttaa siihen rekur- siivisesti. Palautus tapahtuu muuttamalla syötteenä saadun koneen M_wtilojen numerointia niin, ettei tilaa numero 5 käytetä mihinkään, ja vaihtamalla kaikki siirtymät johonkin lopputilaan siir- tymiksi tilaan numero 5. Näin saadaan kone M_w⁰, joka siirtyy tilaan numero 5 (ja hylkää syöt- teensä x) täsmälleen silloin, kun kone M pysähtyy samalla syötteellä. Jos syötteen alkuosa w ei ole validi Turingin koneen koodi, palautus ei tee mitään.

Olkoon

A = fw111x j w on Turingin koneen koodi ja Mw siirtyy tilaan numero 5 syötteellä xg ja f yllä mainittu rekursiivinen palautus. Merkitään f(w111x) = w⁰111x. Nyt pätee

w111x 2 H () w on Turingin koneen koodi ja Mw pysähtyy syötteellä x

() w on Turingin koneen koodi ja M_w⁰ siirtyy tilaan numero 5 syötteellä x () w⁰111x = f(w111x) 2 A:

2. Tehtävänä oli osoittaa, ettei kieli

A = fw₁111w₂j L(M_w1) = L(M_w2); w₁ja w₂Turingin koneen koodejag

ole rekursiivisesti lueteltava. Tämä tapahtuu palauttamalla tyhjyysongelmaa vastaava kieli L= fw 2 f0; 1gj L(M_w) = ;g

kieleen A. Palautus on yksinkertaisesti kuvaus f(w) = w111w⁰, kun w on Turingin koneen koodi, ja f(w) = w⁰111w⁰muuten, missä w⁰on jonkin tunnetun kaikki syötteet hylkäävän koneen koodi.

Nyt siis pätee kaikilla Turingin koneen koodeilla w f(w) 2 A () w111w⁰2 A

() L(M_w) = L(M_w⁰) = ; () w 2 L:

Muilla merkkijonoilla x pätee triviaalisti x 2 L ja f(x) 2 A. Jos siis kieli A olisi rekursii- visesti lueteltava, olisi sen tunnistajakone rekursiivisen palautuksen f kautta tunnistaja myös tyhjyysongelmaa vastaavalle kielelle L, joka ei ole rekursiivisesti lueteltava. Tuloksena olisi näin ristiriita, joten kieli A ei voi olla rekursiivisesti lueteltava.

3. (a) Ongelma voidaan muotoilla formaalina kielenä A =

w 2 f 0; 1 gj 000 2 L(Mw) : Kieli A voidaan esittää muodossa A = LS missä

S =

B f 0; 1 gj B 2 RE ja 000 2 B

= f L(M) j 000 2 L(M) g :

Siis S on määritelmän mukaan semanttinen ominaisuus. Lisäksi S 6= ;, sillä esim. kieli f 000 g kuuluu luokkaan S, ja S 6= RE, sillä esim. tyhjä kieli ; ei kuulu luokkaan S ja on rekursiivisesti lueteltava. Siis Ricen lauseen perusteella ominaisuus S on ratkeamaton, eli kieli A = LS ei ole rekursiivinen.

(b) Määritellään funktio f : f 0; 1 g! f 0; 1 g siten, että f(w) = w111000 kaikilla w 2 f 0; 1 g. Nyt

w 2 A , 000 2 L(Mw) , f(w) 2 Lu

missä on ensin käytetty kielen A määritelmää ja sitten kielen Luja funktion f määritelmää.

Koska f on selvästi rekursiivinen, se on rekursiivinen palautus A _m L_u. Koska L_u on rekursiivisesti lueteltava, myös A on.

4. Väite: Kieli B ei ole rekursiivisesti lueteltava (eikä siis rekursiivinen).

Todistus: Muodostamme palautuksen f : L _m B. Koska L ei ole rekursiivisesti lueteltava, väite seuraa.

Valitaan f(x) = x1 kaikilla x 2 f 0; 1 g. Kielen B määritelmästä nähdään suoraan, että x 2 L, jos ja vain jos f(x) 2 B. Koska f on selvästi rekursiivinen, se on haluttu palautus. 2

Väite: Kieli B ei ole rekursiivisesti lueteltava (eikä siis rekursiivinen).

Todistus: Havaitaan, että

B = f " g [ f x1 j x 2 L g [ f x0 j x 62 L g :

Muodostamme palautuksen g : L mB. Koska L ei ole rekursiivisesti lueteltava, väite seuraa.

Valitaan g(x) = x0 kaikilla x 2 f 0; 1 g. Ylläolevasta kielen B esityksestä nähdään suoraan, että x 2 L, jos ja vain jos g(x) 2 B. Koska g on selvästi rekursiivinen, se on haluttu palautus. 2

2