581336 Laskennan teoria (syksy 2003) Harjoitus 3 (4.7.11.2003)

581336 Laskennan teoria (syksy 2003) Harjoitus 3 (4.7.11.2003)

1. (a) Mikä merkkijono on luennoilla esitetyn numeroinnin mukaanw₁₃?

(b) Esitä jokin koodi luennoilla (s. 26) esitetylle kielen{0ⁿ1ⁿ |n≥1} hyväksyvälle Turingin koneelle.

2. Osoita, että josAjaB ovat rekursiivisesti lueteltavia, niin myösA∪B jaA∩B ovat.

3. Muodosta Turingin koneM, joka laskee funktion f:{0,1}^∗ → {0,1}^∗, missäf(w) =w111w. SiisM lisää nauhalle välimerkin 111 ja sen jälkeen kopioi alkuperäisen syötteen uudelleen.

4. OlkoonL1, . . . , Lk sellainen kokoelma aakkostonΣkieliä, että (a) Li∩Lj =∅kun i6=j,

(b) L1∪L2∪. . .∪Lk= Σ^∗ ja

(c) jokainen kieliL_i on rekursiivisesti lueteltava.

Osoita, että jokainen kieliL_i on rekursiivinen.

5. OlkoonL⊆ {0,1}^∗ jokin rekursiivisesti lueteltava kieli, jollaLei ole rekursiivisesti lueteltava.

Muodostetaan kieli

B={x0|x∈L} ∪ {x1|x6∈L}.

Mitä voidaan päätellä kielen B rekursiivisuudesta tai rekursiivisesta lueteltavuudesta? Entä kielelleB? Perustele. (Vihje: mitä kieliä osaat rekursiivisesti palauttaa kieleenB?)

6. Osoita, että diagonaalikielen Ld komplementti Ld on rekursiivisesti lueteltava. Voit käyttää hyväksi tehtävän 3 konettaM sekä luennolla esitettyä universaalikonettaU.