Next: About this document
Up: No Title
Previous: No Title
-
Merkitään = luvun binääriesityksen n ensimmäistä bittiä.
Arvioi lausekkeiden ja arvoa n:n funktiona.
-
Osoita, että .
-
Osoita, että funktio K(x) ei ole rekursiivinen.
(Vihje: Sovella lauseen 7.7 (ii) todistusideaa.)
Millä aritmeettisen hierarkian tasolla sijaitsee joukko
?
Entä joukko ?
-
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.)
-
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.
-
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ä
.)
- 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):
Pekka Orponen
Thu Mar 30 14:48:03 EET DST 2000