Mathematical logic and foundations Definition

Algorithmic randomness

Builds on Cantor space Computably enumerable set Kolmogorov complexity

Definition

Let $2^\omega$ be Cantor space, the set of infinite binary sequences. For a finite binary string $\sigma$ of length $\abs{\sigma}$ , let $[\sigma] \subseteq 2^\omega$ be the set of sequences that begin with $\sigma$ . Let $\mu$ be the uniform measure on $2^\omega$ , with $\mu([\sigma]) = 2^{-\abs{\sigma}}$ . A Martin-Löf test is a sequence $(U_n)_{n \in \N}$ of subsets of $2^\omega$ such that:

there is a computably enumerable set $W$ of pairs $(n, \sigma)$ with $U_n = \bigcup \set{[\sigma] : (n, \sigma) \in W}$ for every $n$ ;
$\mu(U_n) \le 2^{-n}$ for every $n$ .

A sequence $X \in 2^\omega$ is Martin-Löf random, or algorithmically random, if $X \notin \bigcap_n U_n$ for every Martin-Löf test $(U_n)$ .

Remarks

Example: the binary expansion of Chaitin's halting probability $\Omega$ is Martin-Löf random. Also, the set of non-random sequences has measure $0$ , because there is a universal Martin-Löf test whose intersection contains every non-random sequence.

Non-example: a computable sequence $X$ is not random. Let $X \upharpoonright n$ be the string of the first $n$ bits of $X$ . The sets $U_n = [X \upharpoonright n]$ form a Martin-Löf test: they are uniformly computable and $\mu(U_n) = 2^{-n}$ . And $X$ lies in all of them.

The Levin–Schnorr theorem gives an equivalent form with Kolmogorov complexity. Let $K$ be prefix-free complexity. Then $X$ is Martin-Löf random if and only if there is a constant $c$ with $K(X \upharpoonright n) \ge n - c$ for all $n$ .

Reading path

To understand this page from the ground up, read these 66 pages in order. The foundations come first.

Cantor set example
Compact space concept
Computably enumerable set concept
Element definition
Kolmogorov complexity concept
Metrizable space concept
Product topology concept
Proposition concept
Real numbers object
Totally disconnected space concept
Set definition
Conjunction definition
Disjunction definition
Implication definition
Predicate definition
Empty set object
Family of sets definition
Ordered pair definition
Intersection definition
Union definition
Existential quantifier definition
Universal quantifier definition
Cartesian product definition
Subset definition
Intersection of a family of sets definition
Union of a family of sets definition
Uniqueness quantifier definition
Binary relation definition
Universal set definition
Topological space definition
Complement definition
Function definition
Subspace topology definition
Basis of a topology definition
Codomain definition
Injective function definition
Preimage of a set definition
Product topology definition
Subbasis definition
Metric space definition
Surjective function definition
Product topology on an arbitrary product definition
Open ball definition
Bijective function definition
Metric topology definition
Inverse function definition
Open set definition
Closed set definition
Hausdorff space definition
Continuous map of topological spaces definition
Open cover definition
Complement of an open set is closed statement
Homeomorphism definition
Compact space definition
Continuity via closed sets statement
Compact set definition
Compactness via open covers statement
Closed subsets of compact sets are compact statement
Compact subsets of a Hausdorff space are closed statement
Continuous image of a compact set is compact statement
Product of compact sets is compact statement
Continuous bijection from a compact space to a Hausdorff space is a homeomorphism statement
Tychonoff's theorem statement
Cantor set is homeomorphic to the space of binary sequences statement
Cantor space object
Algorithmic randomness definition

Tag	`X5KD3X3VJ3`
URI	`m2://X5KD3X3VJ3`
Kind	definition
Writing	W0 stub
MSC	03D32, 68Q30
Defines	Algorithmic randomness
Uses	Cantor space, Computably enumerable set, Kolmogorov complexity
Changed	2 November 2026

Algorithmic randomness

Definition

Remarks

Reading path

Further reading

What this page needs for W1

What links here