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 distinguished 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.

Contrast with statistical randomness.

See also

• Algorithmic information theory
• Nothing up my sleeve number

Algorithmic information theory | Randomness