Algorithmic randomness

Summary

Algorithmic randomness makes precise which individual infinite binary sequences are random. The standard notion is Martin-Löf randomness. It calls a sequence random if it passes every effective statistical test, that is, if it avoids every effectively given set of measure zero. Almost every sequence, in the sense of the uniform measure, is random in this sense, while no computable sequence is. The notion connects computability, probability and Kolmogorov complexity.