Kolmogorov Complexity

Motivation: send a program, not a codeword

Every compressor so far needed a model. Huffman and Shannon codes need the distribution $p$ . Universal codes need a family $\{p_\theta\}$ or at least a stationary ergodic source. Lempel–Ziv works on any individual sequence, but it only exploits repetition. And the universal coding note ended with an unsettled question: for one particular string, with no distribution at all, what is the ultimate limit of compression?

Kolmogorov’s answer (1965) changes what gets sent down the wire. The receiving office isn’t a lookup table but a general-purpose computer, the most general decompressor there is. Instead of a codeword, the sender transmits a program that prints the message. The complexity of a message is the length of the shortest such program.

ExampleThree 64-bit strings

0101010101010101010101010101010101010101010101010101010101010101
0110101000001001111001100110011111110011101111001100100100001000
1101111001110101111101101111101110101101111000101110010100111011

String 1 is “print 01 thirty-two times”, a constant-length program.
String 2 passes most statistical tests for randomness, yet it is the start of the binary expansion of $\sqrt2 - 1$ . That is also a constant-length program, and no statistical test would have found it.
String 3 looks random, but has too few zeros. Describing the number of ones $k$ and then the string’s index among strings with $k$ ones takes about $\log n + nH(k/n)$ bits, less than $n$ , but growing with $n$ .

A string of $n$ fair coin flips almost surely has no program shorter than “print the following: …”. There are $2^n$ such strings and not enough short programs to go round.

IntuitionWhat changes compared with entropy

	Entropy	Kolmogorov complexity
Object	A random variable $X \sim p$	A single string $x$
Needs a distribution?	Yes	No
Description of $x$	Shannon codeword, $\approx \log\frac{1}{p(x)}$ bits	Shortest program, $K(x)$ bits
Computable?	Yes, given $p$	No
Connection	$\mathbb{E}K(X^n) \approx H(X^n)$

Kolmogorov complexity is a conceptual precursor of entropy: averaged over a random source, the shortest-program length is the entropy, so the shortest program is a universal code good for every distribution at once.

ImportantA way to think, not an algorithm

The shortest program can’t be found in general; that is a theorem, not an engineering obstacle. The value of the theory is conceptual. It underlies universal codes, gives a foundation for inductive inference, formalizes Occam’s razor, and gives a definition of an individual random sequence. In practice we use short, not shortest, programs.

Models of computation

DefinitionTuring machine (informal)

A finite-state machine with three tapes:

a program tape, read in one direction only, never backing up;
a work tape it can read and write;
an output tape it writes on.

At each step it reads a program symbol, changes state according to a finite transition table, possibly writes on the work and output tapes, and advances the program head.

flowchart LR
  P["Program tape: p1 p2 p3 ... read one way only"] --> M["Finite state machine"]
  W["Work tape"] <--> M
  M --> O["Output tape: x1 x2 ..."]

IntuitionTuring’s model of a human computer

In 1936 Turing asked whether a machine could reproduce what a person does when calculating: think, write a little, think some more, write some more. A finite set of states plays the role of the mind. The alphabet is finite, because infinitely many symbols couldn’t be told apart in finite space.

DefinitionChurch’s thesis

Every sufficiently powerful computational model (Turing machines, the $\lambda$ -calculus, a desktop computer with unbounded memory) computes the same class of functions. That class agrees with the intuitive notion of effectively computable: a finite recipe followed by finitely many mechanical steps. These are the partial recursive functions $f : \{0,1\}^* \rightarrow \{0,1\}^* \cup \{0,1\}^\infty$ . They are “partial” because the computation may never halt, in which case $f$ is undefined there.

DefinitionUniversal computer

A computer $\mathcal{U}$ is universal if it can simulate any other computer $\mathcal{A}$ , given a finite simulation program $s_\mathcal{A}$ describing $\mathcal{A}$ . All but the most trivial computers are universal.

ImportantHalting programs are prefix-free

The program head only moves forward, and the machine stops reading as soon as it halts. So no halting program can be a prefix of another halting program: the machine would have halted before reading the extension. Programs therefore form an instantaneous code, and that single fact makes Kolmogorov complexity formally parallel to information theory.

Definitions and examples

DefinitionKolmogorov complexity

For a universal computer $\mathcal{U}$ and a finite binary string $x$ , with $l(\cdot)$ denoting length,

$K_\mathcal{U}(x) = \min_{p:\ \mathcal{U}(p) = x} l(p)$

the length of the shortest program that prints $x$ and halts.

Component	Detail
Signature	$K_\mathcal{U} : \{0,1\}^* \rightarrow \mathbb{N}$
Domain	One individual finite string, with no distribution attached.
Codomain	A number of bits: the length of the best description.
Depends on	The choice of universal computer, but only up to an additive constant.
Not	Computable: no algorithm outputs $K(x)$ for every $x$ .

IntuitionAn upper bound is a conversation

If you can describe a string to someone else so that they can compute it unambiguously in finite time, the number of bits you used is an upper bound on its complexity. For example, “Print out the first 1,239,875,981,825,931 bits of the square root of e” is 73 ASCII characters, or $8 \times 73 = 584$ bits. That describes a string of more than a quadrillion bits, while most strings that long have complexity close to their length.

DefinitionLength-conditional complexity

If the computer is told the length $l(x)$ in advance,

$K_\mathcal{U}(x \mid l(x)) = \min_{p:\ \mathcal{U}(p, l(x)) = x} l(p)$

NoteA convention not used here

The literature often defines $K(x \mid y)$ as $K(x \mid y, y^*)$ , where $y^*$ is a shortest program for $y$ , to remove some small asymmetries. These notes use the plain definition.

Invariance

TheoremUniversality of Kolmogorov complexity

If $\mathcal{U}$ is universal, then for any computer $\mathcal{A}$ there is a constant $c_\mathcal{A}$ , independent of $x$ , such that

$K_\mathcal{U}(x) \le K_\mathcal{A}(x) + c_\mathcal{A} \qquad \text{for all } x$

ProofPrepend a simulator

Let $p_\mathcal{A}$ be a program with $\mathcal{A}(p_\mathcal{A}) = x$ . The program $s_\mathcal{A}p_\mathcal{A}$ makes $\mathcal{U}$ simulate $\mathcal{A}$ on $p_\mathcal{A}$ , which prints $x$ . Its length is $c_\mathcal{A} + l(p_\mathcal{A})$ with $c_\mathcal{A} = l(s_\mathcal{A})$ . Minimizing over $p_\mathcal{A}$ :

$K_\mathcal{U}(x) \le \min_{p:\ \mathcal{A}(p) = x}\big(l(p) + c_\mathcal{A}\big) = K_\mathcal{A}(x) + c_\mathcal{A}$

∎

CorollaryTwo universal computers agree up to a constant

If $\mathcal{A}$ and $\mathcal{U}$ are both universal, then $|K_\mathcal{U}(x) - K_\mathcal{A}(x)| < c$ for all $x$ . From now on the computer is fixed and dropped from the notation.

WarningThe constant can be enormous

If $\mathcal{A}$ is a mainframe with every software package built in and $\mathcal{U}$ is a bare microprocessor, $s_\mathcal{A}$ contains all of that software. The theory only says something about strings long enough that this fixed cost is negligible. For short strings the constants dominate, and " $K(x) < l(x)$ " (actual compression) can’t be decided by the theory.

Bounds from simple programs

TheoremComplexity is at most the length

$K(x \mid l(x)) \le l(x) + c$

ProofPrint it literally

“Print the following $l$ -bit sequence: $x_1 \cdots x_{l(x)}$ .” Since $l(x)$ is given, the computer knows where the literal ends, so no punctuation is needed. The length is $l(x) + c$ .

∎

TheoremRemoving the length costs about $2\log l(x)$

$K(x) \le K(x \mid l(x)) + 2\log l(x) + c$

ProofSend the length with a doubled-bit comma

Without $l(x)$ the computer must be told where the description ends. To send $n = l(x)$ : write each bit of $n$ ‘s binary expansion twice, then end with 01. For example, $5 = 101_2$ becomes 11 00 11 01. Doubled pairs are always 00 or 11, so the pair 01 is an unambiguous end marker. This costs about $2\log n + 2$ bits.

∎

FormulaIterated-log integer code

Describe $n$ recursively: first the number of bits in $n$ , about $\log n$ , then the bits of $n$ ; and describe that length the same way. The total is

$\log n + \log\log n + \log\log\log n + \cdots = \log^* n$

summing until the terms stop being positive. So

$K(x) \le K(x \mid l(x)) + \log^* l(x) + c$

(Compare the $\log k + 2\log\log k$ integer code in the LZ77 proof.)

Most strings are complex

TheoremLower bound by counting

$\big|\{x \in \{0,1\}^* : K(x) < k\}\big| < 2^k$

ProofThere aren’t enough short programs

The programs of length less than $k$ are the empty string, 0, 1, 00, …, 11…1 ( $k-1$ ones): $1 + 2 + \cdots + 2^{k-1} = 2^k - 1$ of them. Each program prints at most one string, so fewer than $2^k$ strings have complexity below $k$ .

∎

IntuitionPigeonholes, again

This is the same argument behind the McMillan inequality: short descriptions are scarce. Most strings must get long ones.

ConventionBinary entropy function

$H_0(p) = -p\log p - (1-p)\log(1-p)$

$H_0(\frac1n\sum x_i)$ is this function evaluated at the fraction of ones, not the entropy of a random variable. Where no confusion arises we write $H(p)$ .

Examples

Take a computer that accepts unambiguous English commands, with numbers in binary.

Object	Program idea	Complexity
$n$ zeros	”Print the specified number of zeros.”	$K(00\cdots0 \mid n) = c$
$n$ bits of $\pi$	A series for $\pi$	$K(\pi_1\cdots\pi_n \mid n) = c$
`0101…01`	”Print $n/2$ copies of `01`.”	$K(0101\cdots01 \mid n) = c$
Mandelbrot fractal	Iterate $z \mapsto z^2 + c$ from $z = 0$ , colour by escape time	essentially constant
Gotham weather, $n$ days, entropy $\frac15$ bit/day	Fit a Markov model ( $O(\log n)$ bits), then Shannon-code	$\approx \frac n5 + O(\log n) + c$
Mona Lisa, $n$ pixels	An off-the-shelf image compressor, about 3:1	$\le \frac n3 + c$
Integer $n$	Its binary expansion, self-delimited	$\le \log^* n + c$

IntuitionLooks complex versus is complex

The fractal and $\sqrt 2$ look intricate, but both are tiny programs run for a long time. Weather and paintings have structure that a model can exploit, but still need a number of bits proportional to $n$ . The difference between apparent and algorithmic complexity is the whole point of the definition.

Example $n$ bits with $k$ ones

Program: “Generate, in lexicographic order, all sequences with $k$ ones; print the $i$ -th.” The only variables are $k \in \{0, \ldots, n\}$ and $i \in \{1, \ldots, \binom nk\}$ :

$l(p) = c + \underbrace{\log n}_{k} + \underbrace{\log\binom nk}_{i} \le c + \log n + nH_0\!\left(\frac kn\right) - \frac12\log n$

using $\binom nk \le \frac{1}{\sqrt{\pi npq}}2^{nH_0(p)}$ with $p = k/n$ , $q = 1-p$ , for $0 < k < n$ .

TheoremComplexity of a binary string via its count of ones

$K(x_1 x_2 \cdots x_n \mid n) \le nH_0\!\left(\frac1n\sum_{i=1}^n x_i\right) + \frac12\log n + c$

This is the two-stage code of universal coding, now read as a program.

Kolmogorov complexity and entropy

LemmaProgram lengths satisfy Kraft

For any computer $\mathcal{U}$ ,

$\sum_{p:\ \mathcal{U}(p)\text{ halts}} 2^{-l(p)} \le 1$

ProofHalting programs are a prefix code

A halting program can’t be a prefix of another halting program (the machine stops reading once it halts), so the halting programs form a prefix-free set and obey the Kraft inequality.

∎

TheoremExpected complexity equals entropy

Let $X_1, X_2, \ldots$ be i.i.d. $\sim f(x)$ on a finite alphabet $\mathcal{X}$ , with $f(x^n) = \prod_i f(x_i)$ . There is a constant $c$ such that for all $n$ ,

$H(X) \le \frac1n\sum_{x^n} f(x^n)K(x^n \mid n) \le H(X) + \frac{(|\mathcal{X}|-1)\log n}{n} + \frac cn$

Consequently $\frac1n\mathbb{E}K(X^n \mid n) \rightarrow H(X)$ .

ProofLower bound from Kraft, upper bound from a two-stage program and Jensen

Lower bound. Assign each $x^n$ its shortest program. These programs are prefix-free, so their lengths are the lengths of a prefix code for $X^n$ , and by the entropy bound

$\sum_{x^n} f(x^n)K(x^n \mid n) \ge H(X_1, \ldots, X_n) = nH(X)$

Upper bound, binary case. By the count-of-ones theorem,

$\mathbb{E}K(X^n \mid n) \le n\,\mathbb{E}H_0\!\left(\frac1n\sum X_i\right) + \frac12\log n + c \le nH_0\!\left(\mathbb{E}\frac1n\sum X_i\right) + \frac12\log n + c = nH_0(\theta) + \frac12\log n + c$

The middle step is Jensen: $H_0$ is concave.

Upper bound, general alphabet. Describe the type of $x^n$ (the count of each symbol; the last count follows from the others) with $(|\mathcal{X}|-1)\log n$ bits, then its index within the type class, which has fewer than $2^{nH(P_{x^n})}$ members (method of types, Chapter 11):

$K(x^n \mid n) \le nH(P_{x^n}) + (|\mathcal{X}|-1)\log n + c$

Take expectations and apply Jensen to the concave $H$ .

∎

CorollaryWithout the length

$H(X) \le \frac1n\sum_{x^n} f(x^n)K(x^n) \le H(X) + \frac{(|\mathcal{X}|+1)\log n}{n} + \frac cn$

The lower bound holds because shortest programs are again a prefix code. The upper bound uses $K(x^n) \le K(x^n \mid n) + 2\log n + c$ . So $\frac1n\mathbb{E}K(X^n) \rightarrow H(X)$ .

ImportantOne universal code for every source

The shortest-program “code” never looks at $f$ , yet averaged over any i.i.d. source it achieves that source’s entropy, with only $O(\log n)$ bits of overhead. A universal computer is a universal compressor. The catch is that it is not computable.

Kolmogorov complexity of integers

DefinitionComplexity of an integer

$K(n) = \min_{p:\ \mathcal{U}(p) = n} l(p)$ , the complexity of $n$ ‘s binary representation.

TheoremBasic properties

Invariance: $K_\mathcal{U}(n) \le K_\mathcal{A}(n) + c_\mathcal{A}$ .
Upper bound: $K(n) \le \log^* n + c$ .

TheoremInfinitely many integers are complex

There are infinitely many $n$ with $K(n) > \log n$ .

ProofKraft against the harmonic series

By the Kraft lemma, $\sum_n 2^{-K(n)} \le 1$ . Suppose instead that $K(n) < \log n$ for all $n > n_0$ . Then

$\sum_{n > n_0} 2^{-K(n)} > \sum_{n > n_0} 2^{-\log n} = \sum_{n > n_0}\frac1n = \infty$

which is a contradiction.

∎

RemarkHuge but simple

Some enormous integers are simple: $2^{2^{2^{2^2}}}$ and $(100!)!$ have short descriptions. The theorem says such integers are the exception.

Algorithmically random and incompressible sequences

TheoremFew fair-coin sequences compress

If $X_1, \ldots, X_n$ are i.i.d. Bernoulli $(\frac12)$ , then

$\Pr\big(K(X_1\cdots X_n \mid n) < n - k\big) < 2^{-k}$

ProofEach sequence has probability

2^{-n}

; count the compressible ones

$\Pr\big(K(X^n \mid n) < n-k\big) = \sum_{x^n:\ K(x^n \mid n) < n-k} 2^{-n} = \big|\{x^n : K(x^n \mid n) < n-k\}\big|\,2^{-n} < 2^{n-k}2^{-n} = 2^{-k}$

by the counting lower bound.

∎

ExampleFive bits of savings

Fewer than $\frac{1}{32}$ of all $n$ -bit strings can be compressed by 5 bits or more.

DefinitionAlgorithmically random; incompressible

A finite string $x^n$ is algorithmically random if $K(x_1\cdots x_n \mid n) \ge n$ . By counting, at least one exists for every $n$ .
An infinite string $x$ is incompressible if $\displaystyle\lim_{n\rightarrow\infty}\frac{K(x_1\cdots x_n \mid n)}{n} = 1$ .

IntuitionRandomness of an individual sequence

Probability theory can’t call a single string “random”: 0000…0 and any other particular string have the same probability under a fair coin. Kolmogorov complexity can. A string is random if it has no description shorter than itself, so it contains no exploitable pattern.

TheoremStrong law of large numbers for incompressible sequences

If $x_1x_2\cdots$ is incompressible, then

$\frac1n\sum_{i=1}^n x_i \longrightarrow \frac12$

ProofAn unbalanced string would have a short description

Step 1: Upper bound. Let $\theta_n = \frac1n\sum_{i \le n}x_i$ . The count-of-ones program describes $x^n$ in $nH_0(\theta_n) + 2\log n + c$ bits (with a looser cost for sending $k$ ), so

$\frac{K(x^n \mid n)}{n} \le H_0(\theta_n) + 2\frac{\log n}{n} + \frac cn$

Step 2: Lower bound. Incompressibility gives $\frac{K(x^n \mid n)}{n} \ge 1 - \epsilon$ for large $n$ .

Step 3: Combine. $H_0(\theta_n) > 1 - \frac{2\log n + c}{n} - \epsilon$ . Since $H_0$ reaches its maximum value 1 only at $\frac12$ , this pins $\theta_n$ inside $[\frac12 - \delta_n, \frac12 + \delta_n]$ , where $\delta_n \rightarrow 0$ (choose $\delta_n$ with $H_0(\frac12 - \delta_n)$ equal to the bound).

∎

ImportantIncompressible strings pass every computable test

The same argument works for any computable statistical test of randomness. If an incompressible $x$ failed a test, the test itself would be a way to describe $x$ more briefly, which is a contradiction. The algorithmic definition of randomness contains all computable tests at once.

TheoremComplexity concentrates at the entropy

If $X_1, \ldots, X_n$ are i.i.d. Bernoulli $(\theta)$ , then

$\frac1n K(X_1\cdots X_n \mid n) \longrightarrow H_0(\theta) \qquad \text{in probability}$

This strengthens the expected-value theorem by removing the expectation.

ProofUpper tail from the count-of-ones program, lower tail from the typical set

Upper. $K(X^n \mid n) \le nH_0(\bar X_n) + 2\log n + c$ , and $\bar X_n \rightarrow \theta$ in probability (weak law). Since $H_0$ is continuous, $\Pr\big(\frac1nK(X^n \mid n) - H_0(\theta) \ge \epsilon\big) \rightarrow 0$ .

Lower. Split on the typical set $A_\epsilon^{(n)}$ . Fewer than $2^{n(H_0 - c)}$ strings have complexity below $n(H_0 - c)$ , and each typical string has probability at most $2^{-n(H_0 - \epsilon)}$ :

$\Pr\big(K(X^n \mid n) < n(H_0 - c)\big) \le \Pr\big(X^n \notin A_\epsilon^{(n)}\big) + 2^{n(H_0 - c)}\,2^{-n(H_0 - \epsilon)} \le \epsilon + 2^{-n(c - \epsilon)}$

This is small once $c > \epsilon$ and $n$ is large.

∎

Universal probability

IntuitionA monkey at a computer

Feed fair coin flips into a universal computer as its program (a monkey at the keyboard). Most inputs produce garbage or an error. But a program of length $l$ has probability $2^{-l}$ , so short programs dominate, and short programs print structured strings, not random ones. The output distribution is far from uniform: simple strings are much more likely than complex strings of the same length.

DefinitionUniversal probability

$P_\mathcal{U}(x) = \sum_{p:\ \mathcal{U}(p) = x} 2^{-l(p)} = \Pr\big(\mathcal{U}(p) = x\big)$

the probability that a program made of fair coin flips $p_1, p_2, \ldots$ prints $x$ .

Component	Detail
Signature	$P_\mathcal{U} : \{0,1\}^* \rightarrow [0,1]$
Domain	A string.
Codomain	Its probability as the output of a randomly programmed universal computer.
Total mass	$\sum_x P_\mathcal{U}(x) \le 1$ (the shortfall is the chance the program never halts).
Not	Computable.

Theorem $P_\mathcal{U}$ dominates every computer’s output distribution

For every computer $\mathcal{A}$ there is a constant $c'_\mathcal{A}$ (depending only on $\mathcal{U}$ and $\mathcal{A}$ ) such that

$P_\mathcal{U}(x) \ge c'_\mathcal{A}\,P_\mathcal{A}(x) \qquad \text{for all } x$

ProofEvery

\mathcal{A}

-program has a

\mathcal{U}

-program only

c_\mathcal{A}

bits longer

For each $p'$ with $\mathcal{A}(p') = x$ , the program $s_\mathcal{A}p'$ makes $\mathcal{U}$ print $x$ and has length $l(p') + c_\mathcal{A}$ . So

$P_\mathcal{U}(x) \ge \sum_{p':\ \mathcal{A}(p') = x} 2^{-l(p') - c_\mathcal{A}} = 2^{-c_\mathcal{A}}P_\mathcal{A}(x)$

∎

ImportantA mixture of all computable distributions

Any computable distribution on strings can be produced by some computer acting on fair coin flips (by inverting its CDF, the reverse of the probability integral transform). So $P_\mathcal{U}$ dominates every computable distribution, up to a constant factor. It is the Bayesian mixture from universal coding taken to the limit: a prior over all computable models, weighted by $2^{-\text{length}}$ .

RemarkThe universe can’t be shown not to be a monkey at a computer

If both $\mathcal{U}$ and $\mathcal{A}$ are universal, the likelihood ratio $P_\mathcal{U}(x)/P_\mathcal{A}(x)$ stays bounded away from 0 and $\infty$ for every $x$ . Contrast Bernoulli $(\theta_1)$ versus Bernoulli $(\theta_2)$ , where the ratio goes to 0 or $\infty$ with more data. So the hypothesis “the data came from $P_\mathcal{U}$ ” can never be completely rejected for data from any computable source. “The universe is monkeys at a computer” can’t be ruled out. “The universe is monkeys at a typewriter” can.

ExampleShakespeare

Suppose Shakespeare’s works are about $10^6$ bits. A monkey at a typewriter produces them with probability $2^{-1{,}000{,}000}$ . At a computer, the probability is about $2^{-K(\text{Shakespeare})}$ , roughly $2^{-250{,}000}$ if the text compresses about 4:1. That is still tiny, but exponentially larger. A computer turns random input into meaningful output far more often than a typewriter does.

NotePreview

Kolmogorov complexity and universal probability proves $P_\mathcal{U}(x) \approx 2^{-K(x)}$ , so $\log\frac{1}{P_\mathcal{U}(x)}$ (the ideal Shannon code length for the universal distribution) and $K(x)$ are the same complexity measure up to a constant.

The halting problem and noncomputability

IntuitionSelf-reference breaks things

“This statement is false” has no consistent truth value. Neither does the pair “The next statement is false. The preceding statement is true.” In 1931 Gödel encoded statements and proofs as integers and built a statement of this form inside arithmetic, showing that any sufficiently rich mathematical system contains true statements it can’t prove.

TheoremThe halting problem (stated)

There is no algorithm that decides, for every program, whether it halts. This isn’t about any particular program: many can easily be shown to halt or loop. No single procedure works for all of them. The halting problem is a concrete instance of Gödel’s incompleteness theorem, and it marks the boundary between what computers can do with unbounded time and memory and what they can’t do at all.

Theorem $K$ is not computable

No algorithm computes $K(x)$ for every $x$ .

IntuitionWhy the obvious search fails

To find the shortest program for $x$ , try all programs in order of length. But at any moment some short programs are still running, and there’s no way to tell whether they will eventually halt and print $x$ . So you can never certify that no shorter program exists.

RemarkApproximable from above

Running ever more programs for ever longer gives upper bounds on $K(x)$ that converge to the true value. The trouble is that you may already have the shortest program without ever being able to know it.

ExampleThe Berry paradox

“The smallest number not nameable in under ten words.” That phrase has fewer than ten words and names the number, so the number can’t exist, yet some number must fit. The fix is to make “nameable” precise as “describable by a program that prints it”. Then the number exists but is not computable: the phrase describes it but is not a program that computes it. Beckenbach’s version: the smallest “dull” number would be interesting for that very reason.

Chaitin’s $\Omega$

DefinitionHalting probability

$\Omega = \sum_{p:\ \mathcal{U}(p)\text{ halts}} 2^{-l(p)} = \Pr\big(\mathcal{U}(p)\text{ halts}\big)$

for a program $p$ made of fair coin flips. By the Kraft lemma, $0 \le \Omega \le 1$ . Write $\Omega_n = 0.\omega_1\omega_2\cdots\omega_n$ for its first $n$ bits.

Component	Detail
Type	A single real number in $[0,1]$
Meaning	The chance a random program halts
Computable?	No: computing it would solve the halting problem
Information content	Every bit is incompressible

$\Omega$ is a philosopher’s stone

AlgorithmDovetailing: run all programs “in parallel”

List all programs: (empty), 0, 1, 00, 01, 10, 11, 000, …. At stage $t$ , run each of the first $t$ programs for $t$ steps. Every program eventually gets unbounded running time, so every halting program is eventually observed to halt.

Theorem $n$ bits of $\Omega$ decide halting for all programs of length $\le n$

Given $\Omega_n$ , dovetail all programs and add up $2^{-l(p)}$ over those seen to halt, until the running sum reaches $\Omega_n$ . At that point every program of length $\le n$ that will ever halt has already halted.

ProofThe remaining mass is too small for a short program

When the running sum reaches $\Omega_n$ , the mass still to come is at most $\Omega - \Omega_n < 2^{-n}$ . A not-yet-halted program of length $\le n$ would contribute at least $2^{-n}$ if it later halted, which is too much. So none will.

∎

ImportantDeciding mathematics with $\Omega$

Many open problems are questions about whether a search halts:

Fermat’s last theorem: search $x, y, z, n \ge 3$ for $x^n + y^n = z^n$ , halting on a counterexample.
Goldbach’s conjecture: search the even numbers for one that is not a sum of two primes.
Any theorem with a finite proof: search all proofs, halting when one proves it.

So knowing $\Omega_n$ settles every finitely refutable or finitely provable statement expressible in fewer than $n$ bits. It may take an arbitrarily long (but finite) time. Without $\Omega$ , Gödel says no effective procedure can do this. $\Omega$ is an oracle.

RemarkThe most compact oracle

The real number whose $i$ -th bit says whether program $i$ halts carries the same information, but very diluted: you need about $2^n$ of its bits to settle all programs of length less than $n$ . $\Omega$ packs the same knowledge into $n$ bits.

Theorem $\Omega$ is algorithmically random

There is a constant $c$ such that

$K(\omega_1\omega_2\cdots\omega_n) \ge n - c \qquad \text{for all } n$

ProofShort

\Omega_n

would print a complex string cheaply

Step 1: From a shortest program for $\Omega_n$ ( $K(\Omega_n)$ bits), compute $\Omega_n$ . Use it to list every program of length $\le n$ that halts, together with its output.

Step 2: Output the first string $x_0$ that is not on that list. No program of length $\le n$ prints $x_0$ , so $K(x_0) > n$ .

Step 3: Steps 1–2 form a program for $x_0$ of length $K(\Omega_n) + c$ . So $K(\Omega_n) + c \ge K(x_0) > n$ .

∎

Universal gambling

The problem. A gambler bets sequentially on the bits of a string at fair 2-for-1 odds, with no idea where the string comes from. In the horse-race note, the optimal bet was proportional to the true distribution. With no distribution, what should the gambler use?

DefinitionUniversal gambling scheme

Bet $b(x) = 2^{-K(x)}$ on each whole string $x$ . Simple strings get large bets. The bets total $\sum_x 2^{-K(x)} \le \Omega \le 1$ ; assume the unused remainder is thrown away. Betting on whole strings is equivalent to sequential betting (red and black). The wealth after seeing $x$ collects every bet on strings that extend $x$ :

$S(x) = \sum_{x' \sqsupseteq x} 2^{l(x)}b(x')$

TheoremWealth plus complexity is at least length

$\log S(x) + K(x) \ge l(x)$

ProofKeep only the bet on

x

itself

$S(x) \ge 2^{l(x)}b(x) = 2^{l(x)}2^{-K(x)}$ . Take logarithms.

∎

ImportantThe algorithmic conservation law

This is the counterpart of the horse-race conservation law $W^* + H = \log m$ , now for a single string with no distribution: log-wealth plus complexity covers the length. Every bit of structure in the string is a doubling for the gambler.

ExampleWhat universal gambling earns

Simple infinite sequences (finite $K$ , e.g. the digits of $\pi$ ): $S(x_1\cdots x_l) \ge 2^{l - c}$ for all $l$ . Since $2^l$ is the most that $l$ fair bets can ever win, this is asymptotically as good as knowing the sequence in advance.
Bernoulli $(p)$ sequences: $S(X_1\cdots X_n) \ge 2^{n - nH_0(\bar X_n) - 2\log n - c} \approx 2^{n(1 - H_0(p) - o(1))}$ , which to first order is the Kelly rate $1 - H(p)$ of a gambler who knows $p$ .

One scheme, with no model, matches the best model-aware gambler on every computable source. (It is also uncomputable, of course.)

Occam’s razor

ExampleLaplace’s sunrise problem

Laplace modelled sunrises as Bernoulli $(\theta)$ with $\theta$ uniform on $[0,1]$ . After $n$ sunrises in a row,

$P(X_{n+1} = 1 \mid X_1 = \cdots = X_n = 1) = \frac{\int_0^1\theta^{n+1}d\theta}{\int_0^1\theta^n d\theta} = \frac{n+1}{n+2}$

That is the Laplace estimator (see also rule of succession), so $P(\text{no sunrise}) = \frac{1}{n+2}$ .

DerivationThe same problem under universal probability

Next bit 1. The probability of $1^n$ followed by more ones is dominated by the shortest program, “print 1s forever”: $\sum_y p(1^n1y) \approx p(1^\infty) = c > 0$ , independent of $n$ .

Next bit 0. Any program printing $1^n0\ldots$ implicitly describes $n$ , so it has length at least $K(n) \approx \log n$ for most $n$ . Ignoring lower-order terms, $\sum_y p(1^n0y) \approx 2^{-\log n} = \frac1n$ .

Ratio.

$p(0 \mid 1^n) = \frac{p(1^n0)}{p(1^n0) + p(1^\infty)} \approx \frac{1/n}{1/n + c} = \frac{1}{cn + 1}$

IntuitionTwo routes to the same answer

Laplace got $\frac{1}{n+2}$ from an explicit uniform prior. The universal distribution gets about $\frac{1}{cn+1}$ from simplicity alone: a rule that breaks after exactly $n$ steps must encode $n$ , which costs $\log n$ bits, so it is about $n$ times less likely than the rule that never breaks.

DefinitionOccam’s razor

Nunquam ponenda est pluralitas sine necessitate: explanations should not be multiplied beyond necessity. Among explanations consistent with the data, choose the simplest. In this framework, choose the shortest program that produces the data.

ExampleMercury’s perihelion

General relativity explains the precession of Mercury’s perihelion with fewer assumptions than Newtonian gravity patched with an ad hoc $c/r^3$ correction. The shorter explanation wins.

Kolmogorov complexity and universal probability

TheoremEquivalence of $K(x)$ and $\log\frac{1}{P_\mathcal{U}(x)}$

There is a constant $c$ , independent of $x$ , such that

$2^{-K(x)} \le P_\mathcal{U}(x) \le c\,2^{-K(x)} \qquad \text{for all } x$

equivalently

$K(x) - c' \le \log\frac{1}{P_\mathcal{U}(x)} \le K(x)$

IntuitionOne term dominates an infinite sum

Every string has infinitely many programs (pad any program with irrelevant instructions), so $P_\mathcal{U}(x)$ is an infinite sum. The theorem says that sum is within a constant factor of its largest term, $2^{-K(x)}$ . This mirrors $H(X)$ versus $\log\frac{1}{p(x)}$ : in both the probabilistic and the algorithmic worlds, $\log\frac1{\text{probability}}$ is the natural description length.

IntuitionWhy the hard direction should be true

For any computable distribution $p$ , a Shannon–Fano–Elias code describes $x$ in about $\log\frac{1}{p(x)} + c$ bits, so $K(x) \le \log\frac{1}{p(x)} + c$ . The difficulty is that $P_\mathcal{U}$ is not computable, so its Shannon code can’t be built directly. The proof builds the code tree incrementally from better and better lower estimates of $P_\mathcal{U}$ .

ProofEasy direction

If $p^*$ is a shortest program for $x$ , $P_\mathcal{U}(x) = \sum_{p:\ \mathcal{U}(p) = x}2^{-l(p)} \ge 2^{-l(p^*)} = 2^{-K(x)}$ .

∎

ProofHard direction: build the code tree as the estimates improve

We need $K(x) \le \log\frac{1}{P_\mathcal{U}(x)} + c$ .

Step 1: Enumerate halting programs. Dovetail all programs and list the halting ones in the order they halt, with their outputs, $(p_k, x_k)$ . Keep a running lower estimate of each string’s universal probability:

$\hat P_\mathcal{U}(x_k) = \sum_{i \le k:\ x_i = x_k} 2^{-l(p_i)}, \qquad n_k = \left\lceil \log\frac{1}{\hat P_\mathcal{U}(x_k)}\right\rceil$

As more programs for $x$ halt, $\hat P_\mathcal{U}(x) \uparrow P_\mathcal{U}(x)$ and $n_k$ can only decrease.

Step 2: Winnow. Delete any triple $(p_k, x_k, n_k)$ with the same $x$ and the same $n$ as an earlier triple. Now each string appears at most once per level.

Step 3: Assign nodes. Give each surviving triple the first available node at depth $n_k + 1$ of a binary tree, where “available” means not a descendant or ancestor of an already assigned node. This keeps the assignment prefix-free.

Step 4: Kraft guarantees there is always room. For a fixed $x$ , the surviving $n_k$ are distinct integers, each $\ge \lceil\log\frac{1}{P_\mathcal{U}(x)}\rceil$ (since $\hat P_\mathcal{U} \le P_\mathcal{U}$ ). So

$\sum_{k:\ x_k = x}2^{-(n_k+1)} \le \frac12\cdot 2^{-\lceil\log\frac{1}{P_\mathcal{U}(x)}\rceil}\left(1 + \frac12 + \frac14 + \cdots\right) \le P_\mathcal{U}(x)$

Summing over $x$ : $\sum_k 2^{-(n_k+1)} \le \sum_x P_\mathcal{U}(x) \le 1$ . By the Kraft inequality the assignment never runs out of nodes.

Step 5: The tree is a decoder. Describe $x$ by the path $\tilde p$ to its shallowest node. Since $\hat P_\mathcal{U}(x)$ eventually exceeds $P_\mathcal{U}(x)/2$ , that node sits at depth at most $\log\frac{1}{P_\mathcal{U}(x)} + O(1)$ . To print $x$ : rerun the deterministic construction until node $\tilde p$ is assigned, then output its string. This program has length $l(\tilde p) + c$ , so

$K(x) \le \log\frac{1}{P_\mathcal{U}(x)} + c$

∎

ExampleThe construction on a short list

Programs halting in this order (string, then program, then estimate):

$k$	$p_k$	$x_k$	$\hat P_\mathcal{U}(x_k)$	$n_k$	Kept?	Node (depth $n_k+1$ )
1	`10111`	`1110`	$2^{-5}$	5	yes	`000000`
2	`11`	`10`	$2^{-2}$	2	yes	`001`
3	`0`	`1110`	$2^{-5} + 2^{-1}$	1	yes	`01`
4	`1010`	`1111`	$2^{-4}$	4	yes	`00001`
5	`101101`	`1110`	$2^{-1} + 2^{-5} + 2^{-6}$	1	no: repeats $(1110, 1)$	—
6	`100`	`1`	$2^{-3}$	3	yes	`0001`

The string 1110 is now described by the path 01. To print it, run the construction until node 01 is assigned, then execute its program $p_3 =$ 0. The string 1111 is described by 00001.

flowchart TD
  R(("root")) -->|0| A(( ))
  A -->|0| B(( ))
  A -->|1| N3["01: 1110"]
  B -->|0| C(( ))
  B -->|1| N2["001: 10"]
  C -->|0| D(( ))
  C -->|1| N6["0001: 1"]
  D -->|0| E(( ))
  D -->|1| N4["00001: 1111"]
  E -->|0| N1["000000: 1110"]

WarningDecodable, but not encodable

The receiver can rebuild the tree, so this is a genuine program. But the sender has no effective way to find the shallowest node for a given $x$ , because that would require knowing when the estimates stop improving. The theorem shows a short program exists; it doesn’t show how to find it.

The Kolmogorov sufficient statistic

The problem. A Bernoulli $(\theta)$ sample has $K(x^n \mid n) \approx nH_0(\theta) + \frac12\log n$ , much less than $n$ , so the string has structure. What structure? Inspecting the shortest program $p^*$ itself doesn’t help: $p^*$ is incompressible (otherwise $x^n$ would have an even shorter description), so it looks random too.

IntuitionSplit the description into structure and noise

The program “it has $k$ ones, and it is the $i$ -th such string” is optimal to first order, and it is two-stage. The first stage (describe $k$ ) names a set $S = \{x : \sum x_i = k\}$ and contains all the structure. The second stage (the index, $\log|S| \approx nH_0(\theta)$ bits) is pure noise: $x^n$ is maximally complex given $S$ . Generalize this: look for a simple set that contains $x^n$ , then pay $\log|S|$ to point inside it.

DefinitionKolmogorov structure function

$K_k(x^n \mid n) = \min\Big\{\log|S| \;:\; x^n \in S \subseteq \{0,1\}^n,\ \mathcal{U}(p, n) = S \text{ for some } p \text{ with } l(p) \le k\Big\}$

the log-size of the smallest set containing $x^n$ whose indicator function can be printed by a program of at most $k$ bits.

Component	Detail
Signature	$k \mapsto K_k(x^n \mid n)$ , a nonincreasing function of the model budget $k$
Input	$k$ : bits allowed for describing the model (the set)
Output	Bits still needed for the data given the model ( $\log\lvert S\rvert$ )
At $k = 0$	Only $\{0,1\}^n$ is describable, so $K_0 = n$
At $k \ge K(x^n \mid n)$	The singleton $\{x^n\}$ is describable, so $K_k = 0$

DefinitionKolmogorov minimal sufficient statistic

For a small constant $c$ , let $k^*$ be the least $k$ with

$K_k(x^n \mid n) + k \le K(x^n \mid n) + c$

The program $p^{**}$ printing the corresponding set $S^{**}$ is a Kolmogorov minimal sufficient statistic for $x^n$ . Any $p^*$ achieving $K_k + k = K(x^n \mid n)$ is “sufficient”; $p^{**}$ is the shortest of them.

IntuitionReading the structure function

Range of $k$	Behaviour
$0 \le k < k^*$	Each extra model bit captures real structure, and $\log\lvert S\rvert$ drops faster than $k$ grows.
$k = k^*$	The two-stage description first matches the best one-stage description: model + data $\approx K(x^n \mid n)$ .
$k^* < k < K(x^n\mid n)$	Slope $-1$ : each extra model bit just halves the set, encoding noise in the model instead of the data.
$k \ge K(x^n \mid n)$	$K_k = 0$ : the model is the string.

$k^*$ is where structure ends and noise begins. Beyond it, extra model complexity is overfitting.

RemarkParallel with statistical sufficiency

A statistic $T$ is sufficient for $\theta$ when $\theta \rightarrow T(X) \rightarrow X$ is a Markov chain (sufficient statistics). Here $p^{**}$ is sufficient for the structure of $x^n$ : given $S^{**}$ , what remains is incompressible, so nothing further about the structure can be extracted.

ExampleSufficient statistics for three sources

Bernoulli $(\theta)$ . Describing $k$ exactly costs $\log n$ bits, but that is more precision than the data supports. Describe $k$ only to within its natural fluctuation, a bin of width about $\sqrt{n\cdot\frac kn\cdot\frac{n-k}{n}}$ , which costs about $\frac12\log n$ bits. Then index the string among all strings whose count falls in that bin. The total is still $nH_0(\frac kn) + \frac12\log n + o(n)$ , but now $k^* \approx \frac12\log n$ .
First-order binary Markov chain. The sufficient statistic is the Markov type: the counts of 00, 01, 10, 11. Only two of these are free once $n$ is known, each needing about $\frac12\log n$ bits, so $k^* \approx \log n$ .
A noisy grey disc on white (“Mona Lisa”). An $n$ -pixel image ( $\sqrt n \times \sqrt n$ ) shows a disc whose pixels are Bernoulli $(\theta)$ . The model is the disc’s centre and radius (about $(\sqrt n)^3$ distinguishable discs) and its grey level (about $\sqrt n + 1$ levels). That is $\frac32\log n + \frac12\log n$ … the book’s total is $k^* \approx \frac52\log n$ , with the disc’s position and size giving $\frac32\log n$ and the remaining $\log n$ allotted to the grey level and its precision.

IntuitionHalf a log per parameter, once more

Each real parameter, described to the precision the data can resolve, costs about $\frac12\log n$ bits. This is the same overhead found in universal coding, now appearing as the size of the minimal model.

The minimum description length principle

The problem. Data $X_1, \ldots, X_n$ are i.i.d. from some unknown $p \in \mathcal{P}$ . Maximum likelihood picks the $\hat p \in \mathcal{P}$ that makes the data most probable. That works for small model classes, but overfits rich ones.

WarningMaximum likelihood over all distributions memorizes the data

If $\mathcal{P}$ is every distribution on the reals, the maximum likelihood estimate puts mass $\frac1n$ on each observed value. It reproduces the sample exactly and captures none of the underlying structure. Standard remedies assume a parametric family and test the fit, or smooth the estimate (kernel density estimation).

DefinitionMDL estimate

Choose $p \in \mathcal{P}$ to minimize the length of a two-stage description of the data:

$L_p(X_1, \ldots, X_n) = \underbrace{K(p)}_{\text{describe the model}} + \underbrace{\log\frac{1}{p(X_1, \ldots, X_n)}}_{\text{Shannon-code the data given the model}}$

More generally, the minimum description length principle: given data and a set of models, pick the model for which model description plus conditional data description is shortest.

IntuitionMDL penalizes complexity automatically

A more complex model fits better, so $\log\frac1p$ falls, but it costs more to describe, so $K(p)$ rises. The memorizing estimate needs about $n$ numbers to describe, so its model cost explodes. MDL is the practical version of the structure function: stop adding model bits at $k^*$ , where they stop buying more than they cost. It is also Occam’s razor with a price list.

Quick reference

Object	Statement	Reads as
Complexity	$K(x) = \min_{\mathcal{U}(p) = x} l(p)$	Shortest program that prints $x$ .
Invariance	$K_\mathcal{U}(x) \le K_\mathcal{A}(x) + c_\mathcal{A}$	The computer matters only up to a constant.
Length bound	$K(x \mid l(x)) \le l(x) + c$	Never worse than printing it literally.
Unknown length	$K(x) \le K(x \mid l(x)) + \log^* l(x) + c$	Self-delimiting costs about $\log l$ .
Counting	$\lvert\{x : K(x) < k\}\rvert < 2^k$	Most strings are incompressible.
Count of ones	$K(x^n\mid n) \le nH_0(\bar x) + \frac12\log n + c$	Two-stage program.
Kraft	$\sum_{\text{halting } p}2^{-l(p)} \le 1$	Programs are a prefix code.
Entropy	$\frac1n\mathbb{E}K(X^n \mid n) \rightarrow H(X)$	Expected complexity is entropy.
Integers	$K(n) \le \log^* n + c$ ; $K(n) > \log n$ infinitely often
Fair coin	$\Pr(K(X^n \mid n) < n - k) < 2^{-k}$	Random strings are incompressible.
Incompressible	$\frac1n\sum x_i \rightarrow \frac12$	Passes every computable test.
Concentration	$\frac1nK(X^n\mid n) \rightarrow H_0(\theta)$ in probability
Universal probability	$P_\mathcal{U}(x) = \sum_{\mathcal{U}(p) = x}2^{-l(p)}$	Monkey at a computer.
Dominance	$P_\mathcal{U}(x) \ge c_\mathcal{A}P_\mathcal{A}(x)$	Mixture of all computable distributions.
Equivalence	$K(x) - c \le \log\frac{1}{P_\mathcal{U}(x)} \le K(x)$	Complexity is universal surprise.
Noncomputability	$K$ and $\Omega$ are not computable	Halting problem.
$\Omega$	$\sum_{\text{halting }p}2^{-l(p)}$ ; $K(\Omega_n) \ge n - c$	Random, and an oracle for mathematics.
Universal gambling	$\log S(x) + K(x) \ge l(x)$	Algorithmic conservation law.
Occam / Laplace	$p(0 \mid 1^n) \approx \frac{1}{cn+1}$ versus $\frac{1}{n+2}$	Simplicity as a prior.
Structure function	$K_k(x^n\mid n)$ ; sufficient at $k^*$	Where structure ends and noise begins.
MDL	$\min_p\,K(p) + \log\frac{1}{p(X^n)}$	Model cost plus data cost.

Facts to keep to hand

Kolmogorov complexity is entropy without a distribution. Halting programs are a prefix code, so all of source-coding theory applies, and averaged over any computable source $K$ equals $H$ to within $O(\log n)$ .
Counting is the main tool. There are fewer than $2^k$ programs shorter than $k$ . This gives incompressibility of most strings, the $2^{-k}$ tail for fair coins, complex integers, and the randomness of $\Omega$ .
Uncomputable, but approximable from above. You can always find shorter programs; you can never certify that one is shortest. The halting problem is the obstruction, and $\Omega$ packages it into one real number.
$2^{-K(x)} \asymp P_\mathcal{U}(x)$ . Shortest description and universal probability are the same object, exactly as $\log\frac{1}{p(x)}$ is the Shannon description length.
Simplicity is a prior. Universal probability, universal gambling, Laplace’s sunrise, the structure function and MDL are all Occam’s razor made quantitative: each extra bit of description costs a factor of 2 in probability.

References

Cover & Thomas, Elements of Information Theory — Chapter 14

Related

Motivation: send a program, not a codeword

Models of computation

Definitions and examples

Invariance

Bounds from simple programs

Most strings are complex

Examples

Kolmogorov complexity and entropy

Kolmogorov complexity of integers

Algorithmically random and incompressible sequences

Universal probability

The halting problem and noncomputability

Chaitin’s $\Omega$

$\Omega$ is a philosopher’s stone

Universal gambling

Occam’s razor

Kolmogorov complexity and universal probability

The Kolmogorov sufficient statistic

The minimum description length principle

Quick reference

References

Mentioned in

Related

Motivation: send a program, not a codeword

Models of computation

Definitions and examples

Invariance

Bounds from simple programs

Most strings are complex

Examples

Kolmogorov complexity and entropy

Kolmogorov complexity of integers

Algorithmically random and incompressible sequences

Universal probability

The halting problem and noncomputability

Chaitin’s Ω\OmegaΩ

Ω\OmegaΩ is a philosopher’s stone

Universal gambling

Occam’s razor

Kolmogorov complexity and universal probability

The Kolmogorov sufficient statistic

The minimum description length principle

Quick reference

References

Mentioned in

Chaitin’s $\Omega$

$\Omega$ is a philosopher’s stone