Mitä on Kolmogorov-kompleksisuus?

Antti Valmari

Tampereen teknillinen korkeakoulu
Ohjelmistotekniikan laitos
http://www.cs.tut.fi/~ava/
11.10.2000 -- 25.10.2000

Oletetaan, että nollan ja ykkösen a priori todennäköisyydet ovat yhtä suuret. (Niinhän ohjelmoinnissa usein on, tai ainakin niin oletetaan ellei ole erityistä syytä olettaa toisin.) Ajatellaanpa bittijonoja

111111111111111111111111111111111111111111111111111111111111111111111111
010100110100101010101010010101011011100101010101110101010110011010101010

Shannonin informaatioteorian mielestä molemmissa on sama määrä informaatiota, kun niissä kerran on sama määrä bittejä. Kuitenkin pelkkää ykköstä sisältävä jono tuntuu jotenkin epäinformatiiviselta. Kolmogorov-kompleksisuus on vaihtoehtoinen tapa mitata informaatiota, joka ottaa tämän huomioon.

Kolmogorov-kompleksisuuden määrittelemiseksi on ensin valittava ohjelmointikieli tai jokin muu Turing-vahva laskennan formalismi. Sen jälkeen äärellisen merkkijonon Kolmogorov-kompleksisuus on lyhimmän sellaisen syötteettömän ohjelman pituus, joka tulostaa kyseisen merkkijonon ja sitten pysähtyy. Jatkossa oletan, että valittu formalismi muistuttaa tavallisia ohjelmointikieliä.

Merkkijonon Kolmogorov-kompleksisuus on ym. oletuksella aina O(n), missä n on merkkijonon pituus. ("O(n)" tarkoittaa: enintään c1 + c2·n, missä c1 ja c2 ovat jotkin vakiot.) Merkkijonoista vain mitättömän pienen osan Kolmogorov-kompleksisuus on selvästi alle tuon maksimin. Tämä johtuu siitä, että lyhyitä ohjelmia on vain vähän verrattuna pitkien ohjelmien määrään.

Merkkijonon Kolmogorov-kompleksisuus on mahdollista selvittää vain poikkeustapauksissa. On olemassa raja M siten, että yhtään ainutta väitettä muotoa "tämän merkkijonon Kolmogorov-kompleksisuus on vähintään M" ei voi todistaa. Tästä saamme yhdellä iskulla äärettömän joukon muodoltaan yksinkertaisia matemaattisia väittämiä, joista melkein kaikki ovat tosia, mutta ainuttakaan ei voi todistaa todeksi! Tällä on myös oma merkityksensä esimerkiksi pohdittaessa sitä, kuinka paljon informaatiota DNA oikeastaan sisältää.

Kolmogorov-kompleksisuuden avulla voidaan määritellä nollan ja ykkösen välillä oleva luku, jonka biteistä ei voida tietää kuin äärellinen määrä, mutta jolle silti voidaan laskea mielivaltaisen tarkka alalikiarvo. Tämä voi kuulostaa paradoksaaliselta. Paradoksin ratkaisu on siinä, että kun likiarvoa lasketaan, on jonkin rajan jälkeen mahdotonta tietää, joko saavutettu likiarvo on niin-ja-niin tarkka. Siis lopulta likiarvo on aika tarkka, mutta emme voi tietää, milloin! Tämä luku on nimeltään Chaitinin Omega. ("Omega" tarkoittaa sitä kreikkalaista kirjainta, joka muistuttaa aika lailla hevosenkenkää, ja on myös Ohmin sekä asymptoottisen alarajan merkki.)

Chaitinin Omegassa on muutakin hauskaa. Vaikka sen bittiesitys on deterministinen, mikään testi ei pysty erottamaan sitä aidosti satunnaisesta.

Kolmogorov-kompleksisuus asettaa äärimmäisen rajan tiedon pakkaamiselle. Mitään tietoa ei mitenkään voi pakata pienempään tilaan kuin sen Kolmogorov-kompleksisuus ilmoittaa. Kolmogorov-kompleksisuuden selvittämisen mahdottomuudesta johtuu, että pitkän merkkijonon tapauksessa emme koskaan voi tietää, voisiko sen jollakin tuntemattomalla keinolla saada pakattua vielä pienempään tilaan kuin mihin siihen mennessä olemme onnistuneet sen pakkaamaan. Toisin sanoen, emme koskaan voi olla varmoja, että olemme keksineet parhaan pakkausalgoritmin.

Lisätietoja löytyy muun muassa alan uranuurtajan G. J. Chaitin:in kotisivulta. Myös comp.theory.faq:issa on lyhyt luku aiheesta. Kolmogorov-kompleksisuus tunnetaan myös nimillä algoritminen informaatio, algoritminen kompleksisuus jne. Alan pioneereja olivat Chaitin:in ja A. N. Kolmogorov:in lisäksi R. J. Solomonoff. Yksi hyvä paperimuodossa oleva lähde on Ming Li ja Paul M. B. Vitányi: Kolmogorov Complexity and its Applications, Handbook of Theoretical Computer Science Volume A, sivut 187--254.

Kiitokset kommentista Jukka Teuholalle.