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

1. Osoita, luentojen Lauseen 1.11 (ii) nojalla, että kaikilla on (Lause 1.11 (i)).
2. Merkitään kielestä otettujen A äärellisten jonojen muodostamaa kieltä

   

   Osoita, että jos , , niin myös , . (Tämä aputulos, relativoidussa muodossaan, oli keskeisellä sijalla luentojen Lauseen 1.11 (ii) todistuksessa. Tuloksen oikeellisuus on melko helppo todeta tapauksessa , mutta tapaus vaatii mutkikkaamman ns. pyyhkäisysimuloinnin (engl. dovetailing), jossa ensin simuloidaan haluttua laskentaa tietty määrä askelia yhdellä syötteellä, ja askellaskurin tultua täyteen siirrytään toiseen syötteeseen.)

3. Olkoon vastaava oraakkelikoneiden luettelointi kuin aiemmin on muodostettu standardimallisille Turingin koneille, ja olkoon A jokin aakkoston kieli. Osoita, että kieli

   

   kuuluu luokkaan , mutta ei luokkaan . Päättele tästä, että aritmeettinen hierarkia on ääretön, so. että kaikilla on (luentojen Lause 1.6 (ii)), ja siis erityisesti mikään -täydellinen kieli ei voi kuulua luokkaan , kun .

4. Osoita, että aakkoston kielten välinen Turing-palautus on refleksiivinen ja transitiivinen relaatio. Päättele tästä edelleen, että kielten ratkeavuusasteiden

   

   joukossa määritelty relaatio

   

   on osittainjärjestys, jonka minimialkio on . Totea, tehtävän 3 tulokseen nojaten, että asteiden joukossa määritelty ns. hyppyoperaatio (engl. jump operation)

   

   on hyvin määritelty ja tuottaa jokaiselle asteelle asteen , jolla (so. , mutta ei ). Mikä on aste ?

5. Osoita, että kaikki säännölliset kielet kuuluvat luokkaan .
6. Tarkasta Laskennan teoria -monisteen Lauseiden 7.7 ja 7.8 todistuksissa esitetyt diagonalisointiargumentit, joilla osoitetaan että kieli ei kuulu luokkaan ja kieli ei kuulu luokkaan . Kiinnitä erityistä huomiota todistuksissa väitettyjen aikarajojen pitävyyteen.

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