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

1. Suunnittele kombinaatiopiirit seuraavien funktioiden toteuttamiseen:
   1. jos ja vain jos jollakin .
   2. jos ja vain jos .
   Voit yksinkertaisuuden vuoksi olettaa, että kantaporttina on käytettävissä AND-, OR- ja NOT-porttien lisäksi myös kahden bitin XOR. Mikä on suunnittelemiesi piirien koko ja syvyys?
2. Totea, että mikä tahansa n muuttujan Boolen funktio voidaan laventaa seuraavasti:

   

   Minkä kokoinen kombinaatiopiiri funktiolle f saadaan tästä kehitelmästä? Sovella kehitelmää funktioon

   

3. [Jatkoa edelliseen.] Osoita, että mikä tahansa Boolen funktio voidaan laskea kombinaatiopiirillä, jonka koko on porttia. (Idea: Muodosta edellisen tehtävän konstruktiota soveltaen piiri, joka sopivasti valitulla parametrin k arvolla toisaalta laskee kaikki k muuttujan Boolen funktiot, toisaalta koostaa halutun n muuttujan funktion f sen k muuttujan alifunktioista, so. käyttäen edellisen tehtävän lavennuskaavaa n-k kertaa.)
4. Kieltä T, joka sisältää pelkästään muotoa olevia merkkijonoja (so. ) sanotaan laskurikieleksi (engl. tally language). Osoita, että

   

5. 1. Osoita, että luokka P/poly sisältää myös ei-rekursiivisia kieliä.
   2. Osoita, että . (Vihje: Muodosta luokat erottava laskurikieli.)
6. Osoita, että mitään -palautusten suhteen ESPACE-kovaa kieltä ei voida tunnistaa polynomista kokoa olevilla kombinaatiopiireillä. Onko tulos voimassa myös -palautuksille?