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

1. Merkitään = luvun binääriesityksen n ensimmäistä bittiä. Arvioi lausekkeiden ja arvoa n:n funktiona.
2. Osoita, että .
3. Osoita, että funktio K(x) ei ole rekursiivinen. (Vihje: Sovella lauseen 7.7 (ii) todistusideaa.) Millä aritmeettisen hierarkian tasolla sijaitsee joukko ? Entä joukko ?
4. Osoita, että kaikilla on voimassa: . (Tässä on siis samaistettu binäärijonot x ja luonnolliset luvut n vastaavuuden välityksellä. Tulos osoittaa, että vaikka funktion K(x) arvo vaihtelee jatkuvasti rajojen m(x) ja välissä, niin sen muutosnopeus on melko rauhallinen.)
5. Olkoon A rekursiivisesti lueteltava joukko. Osoita, että jos , |x| = n, niin . Päättele tästä, että ``epätyypilliset joukot sisältävät vain yksinkertaisia alkioita'' siinä mielessä, että jos A on rekursiivisesti lueteltava joukko, jolla , niin kaikilla , x = n, on voimassa , missä . Arvioi edelleen sellaisten binäärijonojen Kolmogorov-kompleksisuutta, jotka sisältävät vähintään kaksi kertaa niin paljon ykkösiä kuin nollia.
6. Osoita, että on olemassa säännöllisiä kieliä, jotka voidaan tunnistaa n-tilaisella epädeterministisellä automaatilla, mutta joiden tunnistaminen deterministisellä automaatilla vaatii vähintään tilaa. (Vrt. Laskennan teoria, Lauseet 2.1 ja 2.2. Vihje: Tarkastele kieliä .)
7. Tarkastellaan n solmun täydellisen verkon kaarien värityksiä ``sinisiksi'' ja ``punaisiksi''. Annetulla on Ramseyn luku r(k) pienin sellainen n, jolla verkko välttämättä sisältää joko ``kokonaan sinisen'' tai ``kokonaan punaisen'' k solmun klikin, so.\ yhtenäisesti väritetyn k solmun täydellisen aliverkon. (Tiedetään, että r(k) on äärellinen kaikilla k, mutta ainoat tarkasti tunnetut arvot ovat r(3)=6 ja r(4)=18.) Todista seuraava alarajatulos (P. Erdös 1947):