# Kolmogorov complexity

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?

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.

Title Kolmogorov complexity KolmogorovComplexity 2013-03-22 13:43:41 2013-03-22 13:43:41 tromp (1913) tromp (1913) 9 tromp (1913) Topic msc 68Q30 algorithmic information theory algorithmic entropy