The Levin-Schnorr theorem, Chaitin's Ω, and effective Hausdorff dimension — the deepest connections between complexity and randomness.
Chapter 4 introduced prefix complexity K(x) for finite strings. But Martin-Löf randomness is defined for infinite sequences. To bridge the gap, we need a complexity notion that respects the structure of infinite sequences — specifically, that extending a string can only increase the complexity.
Monotone complexity KM(x) does this: if x is a prefix of y, then KM(x) ≤ KM(y). This monotonicity is natural for infinite sequences: knowing more bits shouldn't make things simpler.
All three agree up to O(log n) for strings of length n, but the fine distinctions matter for the theorems that characterize randomness precisely.
A semimeasure on the binary tree is a function μ: Σ* → [0, ∞) satisfying:
This says that the "mass" at node x is at least the sum of the masses at its children. Some mass may be "lost" at each level — the inequality is not necessarily tight.
If μ(λ) ≤ 1 (where λ is the empty string / root), then μ induces a semimeasure on Ω via μ(Ωx) = μ(x).
A maximal lower semicomputable semimeasure on the tree exists, analogous to the maximal semimeasure on N from Chapter 4. Its negative logarithm gives a priori complexity on the tree.
Let M be the maximal lower semicomputable semimeasure on the binary tree. The a priori complexity is:
Since M is monotone on the tree (M(x) ≥ M(x0) + M(x1) ≥ M(x0)), we have KA(x) ≤ KA(x0) and KA(x) ≤ KA(x1). In words: KA is monotone — it can only increase as we extend the string.
There's another way to define monotone complexity, using monotone machines. A monotone machine is a partial computable function D: Σ* → Σ* with a monotonicity constraint: if p is a prefix of q and both D(p) and D(q) are defined, then D(p) is a prefix of D(q).
Monotone complexity KM(x) is the length of the shortest program p such that D(p) starts with x (D(p) has x as a prefix).
where ⊑ means "is a prefix of or equal to."
The relation: KA(x) = KM(x) + O(1). A priori complexity and monotone complexity are essentially the same thing, approached from different directions (probabilistic vs. computational).
This is the theorem that ties everything together. It gives a precise complexity characterization of Martin-Löf randomness.
In words: ω is random iff its prefixes are incompressible. The prefixes of a random sequence cannot be compressed by more than a constant number of bits, no matter how long they get.
Both directions are non-trivial:
Chaitin defined a remarkable real number:
Here U is the optimal prefix machine and the sum is over all programs p on which U halts. By Kraft's inequality, Ω ≤ 1, so Ω is a real number between 0 and 1.
Ω is computably enumerable from below (lower semicomputable): by running all programs in parallel and adding 2−|p| whenever a program p halts, we get an increasing sequence of rationals converging to Ω. But Ω is not computable — knowing its first n bits would let us solve the halting problem for all programs of length ≤ n.
So Ω is a single real number that concentrates the unsolvability of the halting problem into a sequence of digits. It is random, it is non-computable, and it is definable in a few lines.
Classical Hausdorff dimension measures the "fractal dimension" of sets. The effective version replaces arbitrary covers with computable covers, giving a dimension notion that connects to complexity.
For ML-random sequences, dim(ω) = 1 (prefixes are incompressible, so K/n → 1). For computable sequences, dim(ω) = 0 (prefixes have complexity O(1)). Sequences in between have fractional dimension.
Effective Hausdorff dimension gives a continuous measure of randomness, interpolating between fully computable (dimension 0) and fully random (dimension 1).
Martin-Löf randomness generalizes beyond the uniform measure. For any computable measure μ on Ω, we can define ML-randomness with respect to μ.
A sequence ω is ML-random with respect to μ iff ω does not belong to any μ-effectively null set. Equivalently, K(ω[0..n)) ≥ −log μ(Ωω[0..n)) − O(1).
Different measures give different random sequences. A sequence that is random for Bernoulli(1/2) (fair coin) is not random for Bernoulli(1/3) (biased coin), and vice versa. Randomness is always relative to a measure.
The simulation below approximates Ω by running "programs" (small random computations) and accumulating 2−|p| for each halting program. The sum grows from below, approaching Ω but never reaching it.
Each step simulates checking one more program. Halting programs contribute 2−|p| to the running sum. Watch the lower bound converge.
| Concept | Key fact |
|---|---|
| Monotone complexity KM | KM(x) ≤ KM(xy) for all y — monotone in prefix order |
| KA = KM + O(1) | A priori complexity = monotone complexity |
| Levin-Schnorr | ω is ML-random iff K(ω[0..n)) ≥ n − O(1) for all n |
| Ω | Halting probability; ML-random; lower semicomputable; encodes halting problem |
| Effective dimension | dim(ω) = lim inf K(ω[0..n))/n |