Martin-Löf randomness

Martin-Löf randomness is the most widely studied definition of algorithmic randomness, introduced by Swedish mathematician Per Martin-Löf in 1966. A sequence is Martin-Löf random if and only if it passes every effectively computable statistical test for randomness — or equivalently, if its initial segments have Kolmogorov complexity asymptotically equal to their length. This definition elegantly unifies the statistical and algorithmic approaches to randomness: a Martin-Löf random sequence is one that exhibits no regularity detectable by any algorithmic procedure.

The definition gives rise to a hierarchy of randomness notions. Schnorr randomness and Kurtz randomness provide weaker criteria that are still computationally meaningful. The study of these hierarchies reveals that randomness is not a binary property but a spectrum of algorithmic unpredictability.