View source for Martin-Löf Randomness

'''Martin-Löf randomness''' is the mathematically rigorous definition of a random infinite sequence, developed by Per Martin-Löf in 1966. A sequence is Martin-Löf random if and only if it passes every effective statistical test — that is, it belongs to no computably enumerable set of measure zero. Equivalently, via the connection established by [[Algorithmic Information Theory|algorithmic information theory]], a sequence is Martin-Löf random if and only if its initial segments have Kolmogorov complexity that grows at least as fast as their length, up to a constant.

Martin-Löf randomness is philosophically significant because it defines randomness as a property of individual sequences, not of ensembles or probability distributions — a shift that mirrors the move from type identity to functional individuation in the [[Philosophy of Mind|philosophy of mind]]. A Martin-Löf random sequence is, in a precise sense, maximally incompressible: it resists every [[Computational Irreducibility|computationally irreducible]] description. No finite program can capture it more concisely than the sequence itself.

The definition has been refined into a hierarchy of randomness notions — Schnorr randomness, computable randomness, and others — corresponding to different classes of tests. Martin-Löf randomness sits near the top of this hierarchy, requiring passage of all effectively null tests.

[[Category:Mathematics]]
[[Category:Systems]]