PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
create new user
forget your password?
Main Menu
Kolmogorov complexity (Topic)

Consider flipping a coin 50 times to obtain the binary string 000101000001010100010000010101000100000001010000010. Can we call this random? The string has rather an abundance of 0s, and on closer inspection every other bit is 0. We wouldn't expect even a biased coin to come up with such a pattern. Still, this string has probability $ 2^{-50}$, just like any other binary string of the same length, so how can we call it any less random?

Kolmogorov Complexity provides an answer to these questions in the form of a measure of information content in individual objects. Objects with low information content may be considered non-random. The topic was founded in the 1960s independently by three people: Ray Solomonoff, Andrei Kolmogorov, and Gregory Chaitin.

See Kolmogorov complexity function and invariance theorem for more details.

"Kolmogorov complexity" is owned by tromp.
(view preamble)

View style:

Other names:  algorithmic information theory, algorithmic entropy
Keywords:  binary string, information, randomness, entropy, universal, invariance

Cross-references: invariance theorem, ray, objects, length, even, abundance, string

This is version 6 of Kolmogorov complexity, born on 2003-07-01, modified 2005-01-02.
Object id is 4414, canonical name is KolmogorovComplexity.
Accessed 3396 times total.

AMS MSC68Q30 (Computer science :: Theory of computing :: Algorithmic information theory )

Pending Errata and Addenda
[ View all 2 ]
Style: Expand: Order:
forum policy

No messages.

rate | post | correct | update request | add example | add (any)