Chaitin–Kolmogorov randomness: Encyclopedia - Chaitin–Kolmogorov randomness

Chaitin–Kolmogorov randomness

Chaitin-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. It is fairly easy to see that most strings of a given length are close to random in this sense.

Chaitin-Kolmogorov randomness distinguishes, at least in principle, between numbers that are generated by pseudo-random number generators and true random numbers. However pseudo-random number generators and true random numbers are only distingushed in the limit. Any finite sequence of numbers no matter how apparently random can be generated by a large enough computer program while conversely a truly random sequence of numbers can have an arbitrarily long apparently non-random initial segment. In fact Chaitin's incompleteness theorem shows that though we know that most strings are random in the above sense, the fact that a specific string is random can never be proven, if the string's length is above a certain threshold.

Contrast with statistical randomness.

See also

• Algorithmic information theory
• Nothing up my sleeve number

Adapted from the Wikipedia article "Chaitin–Kolmogorov randomness", under the G.N U Free Docmentation License. Please also see http://en.wikipedia.org/wiki