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