View source for 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.

[[Category:Mathematics]] [[Category:Logic]]