Kolmogorov randomness
From Wikipedia, the free encyclopedia
 |
This article or section may be confusing or unclear for many readers. Please improve the article or discuss this issue on the talk page. This article has been tagged since December 2006. |
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
 |
This statistics-related article is a stub. You can help Wikipedia by expanding it. |
