Algoritmiteorian jatkokurssi, kevät 1999
Harjoitus 2, 12.4. klo 10-12 sali MaD380

1. Palautetaan mieleen, että funktio on tilakonstruoituva, jos jollakin deterministisellä moninauhaisella Turingin koneella M on voimassa: kaikilla syötejonoilla x. Todista seuraavat väitteet:
   1. Funktiot s(n) = k (vakio), s(n) = n ja ovat tilakonstruoituvia.
   2. Jos ja ovat tilakonstruoituvia, niin myös , ja ovat tilakonstruoituvia.
   3. Jokaisella rekursiivisella funktiolla r(n) on olemassa tilakonstruoituva .
2. Todista, että jokaisella tilakonstruoituvalla on voimassa sisältyvyys

   

   (Vihje: Muodosta verkko, jonka solmut ovat simuloitavan epädeterministisen koneen tilannekuvauksia.)

3. Todista seuraava väite: Olkoon ( ), missä q on polynomi ja ( ), . Olkoon toinen polynomi. Tällöin on olemassa ( ), jolla ( ).
4. Todista, että polynomisen aikavaativuushierarkian luokilla , , on seuraavat sulkeumaominaisuudet (luentomuistiinpanojen Lause 2.8, s. 13):
   1. Jos ( ), niin , ( ).
   2. Jos ( ) ja , niin ( ).
   3. Jos ( ), , ja ( ), q polynomi, niin ( ).
   (Sovitaan täsmällisyyden vuoksi, että polynomisen hierarkian luokkien määrittelyssä käytetään parikoodausfunktiota , missä , ja tästä edelleen johdettua jonokoodausfunktiota .)

Huom.: Pääsiäisloman takia kurssilla ei ole ohjelmaa 5.4. eikä 7.4. Seuraavat demot ja luennot ovat maanantaina 12.4.