Tietojenkäsittelyteoria, kevät 2000
Harjoitus 1, to 27.1. klo 10-12 sali MaD381

Tehtävää 1 lukuunottamatta kaikkien seuraavien tehtävien ratkaisussa saa käyttää hyväksi Churchin-Turingin teesiä, jonka mukaan mikä tahansa intuitiivisesti ``mekaaninen'' laskurutiini (algoritmi) voidaan toteuttaa myös Turingin koneella. Tunnetuiksi saa olettaa myös Kleenen kvanttorikarakterisoinnin luokalle RE (luentojen Lause 1.1) sekä luokkien RE ja REC Laskennan teoria -monisteen luvussa 6 esitellyt perusominaisuudet.

1. Laadi Turingin kone, joka tunnistaa aakkoston parillisen pituisten palindromien muodostaman kielen . (Merkintä tarkoittaa merkkijonoa w takaperin kirjoitettuna, so. jos , niin .) Esitä koneen tilannejonot sen käsitellessä syötteitä 0110 ja 1011.
2. Todista seuraavat aritmeettisen hierarkian kieliluokkien ominaisuudet.
   1. .
   2. Kaikilla : jos ( ), niin ( ).
3. Todista oikeaksi aritmeettisen hierarkian kieliluokkien kvanttorikarakterisointi (luentojen Lemma 1.4): kieli , jos ja vain jos on olemassa kieli siten, että kaikilla :

   

   missä

4. Todista, että aritmeettisen hierarkian luokilla , , on seuraavat sulkeumaominaisuudet (luentojen Lemmat 1.5 ja 1.7).
   1. Jos , niin , .
   2. Jos , , niin .
   3. Jos ja , niin .
5. Tutustu Laskennan teoria -monisteen Lauseen 6.11 ja/tai Lauseen 6.12 todistukseen (monisteen ss. 88-92) ja osoita vastaavaa tekniikkaa käyttäen, että kieli

   

   ei ole rekursiivinen.

6. Määritä, millä aritmeettisen hierarkian tasolla (enintään) sijaitsevat seuraavat joukot:
   1. 
   2. 
   3. 

Huom.: Luennoijan virkamatkan takia kurssilla ei ole luentoa tiistaina 2.2.