Algorithmic Randomness

Origin. Per Martin-Löf, "The definition of random sequences" (1966), giving the first definition that survived. Levin and Chaitin gave the incompressibility characterization (1970s); Schnorr gave the martingale one (1971). Developed by Kučera, Solovay, Downey, Hirschfeldt, Nies. The subject is the recursion theory of what a random object is.

Models. A sequence is random when nothing effective can pick it out. Three unrelated-looking ways of saying that — it passes every effective statistical test, it is incompressible, no computable betting strategy wins against it — turn out to define the same class, and the coincidence is the reason the notion is taken to be the right one.

Formalism.

Martin-Löf test: A uniformly Σ⁰₁ sequence (U_n) with μ(U_n) ≤ 2⁻ⁿ. X is ML-random iff X ∉ ⋂_n U_n for every such test. There is a universal test, so ML-randomness is a single condition.

Levin–Chaitin (incompressibility): X is ML-random iff ∃c ∀n : K(X↾n) ≥ n − c, where K is prefix-free Kolmogorov complexity. An initial segment is never compressible by more than a constant.

Schnorr (unpredictability): A martingale d satisfies d(σ) = (d(σ0) + d(σ1))/2. X is ML-random iff no c.e. martingale succeeds on X (lim sup d(X↾n) = ∞). No effective betting strategy makes unbounded money.

Schnorr's theorem: The three definitions coincide. This is the subject's founding fact.

The hierarchy: computable-random ⊋ Schnorr-random ⊋ ML-random ⊋ weak-2-random ⊋ 2-random Each inclusion is strict; the notions are distinguished by the strength of the test.

Chaitin's Ω: Ω = Σ_{p halts} 2^−|p| Left-c.e. and ML-random. The first natural example.

van Lambalgen's theorem: X ⊕ Y is random iff X is random and Y is random relative to X. Randomness behaves like probabilistic independence.

Kučera–Gács: Every set is computable from an ML-random set. Randomness does not bound computational strength.

Symbols.

Metatheory. The coincidence of measure-theoretic, information-theoretic, and game-theoretic definitions is the whole case for ML-randomness being the notion rather than a notion — no other point in the hierarchy has it. Above it, 2-randomness is characterized by unbounded plain complexity (Nies–Stephan–Terwijn); below it, Schnorr randomness lacks a universal test and behaves worse. The interaction with the Turing degrees is the subject's second half: Kučera–Gács shows randomness is compatible with arbitrary computational strength, while the K-trivials — the antipodes of randomness — form a natural class with several independent characterizations.

Applies to. Recursion theory and the degree structure. Algorithmic information theory. Foundations of probability, where it gives a per-object rather than per-distribution notion. Effective measure theory. Randomness tests in practice, at a remove — the definitions are uncomputable.

Limitations. Every notion here is uncomputable: no algorithm decides randomness, and Ω is definable and not computable. The class of random sequences has measure one and contains nothing you can exhibit, so the theory characterizes almost everything and identifies nothing. The hierarchy's naturalness is contested below ML-randomness — Schnorr's own objection was that ML-randomness is too strong to be effective, and that objection has never been settled so much as set aside.

© 2026 Lingenic LLC