Kolmogorov randomness

From Wikipedia, the free encyclopedia

Kolmogorov randomness (also called algorithmic randomness) defines a string (usually of bits) as being random if and only if it is shorter than any computer program that can produce that string. This definiton of randomness is critically dependent on the definition of Kolmogorov complexity. To make this definition complete, a computer has to be specified, usually a Turing machine. According to the above definition of randomness, a random string is also an "incompressible" string, in the sense that it is impossible to give a representation of the string using a program whose length is shorter than the length of the string itself. However, it must also be noted that according to this definition, most strings shorter than a certain length end up to be (Chaitin-Kolmogorovically) random because the best one can do with very small strings is to write a program which simply prints these strings.

Contrast this with statistical randomness.

[edit] See also

• Algorithmic information theory
• Nothing up my sleeve number
• Kolmogorov complexity