Contents / Information Theory / Algorithmic Information Theory

Chapter 15

Algorithmic Information Theory

Kolmogorov complexity: the information in a single object, its relationship to entropy, and the results its uncomputability forces.

Introduction

Shannon's theory measures the information in a source: you must hand it a probability distribution before it will say anything. But the objects we actually hold — a file, a genome, the first million digits of $π$ — arrive one at a time, with no ensemble attached. Algorithmic information theory answers the question Shannon's theory cannot even ask: how much information is in this object?

The answer, due independently to Solomonoff (1964), Kolmogorov (1965) and Chaitin (1969), is disarmingly simple. The information in $x$ is the length of the shortest program that prints $x$ . Everything in this chapter — the invariance theorem, the coincidence of the average of $K$ with Shannon's $H$ , the uncomputability of $K$ , Chaitin's incompleteness theorem, Martin-Löf randomness, $Ω$ , and Solomonoff's induction theorem — unfolds from that one definition.

15.1Describing an Individual Object

A description of a string is anything from which the string can be mechanically recovered. To make that precise we fix the decoding machinery first and then ask how short a description can be.

Definition 15.1 (Description method and its complexity). A description method is a partial computable function $φ : {0, 1}^{*} \to {0, 1}^{*}$ . A string $p$ is a $φ$ -description of $x$ when $φ (p) = x$ . The complexity of $x$ with respect to $φ$ is

C_{φ} (x) = min {∣ p ∣ : φ (p) = x},

with $C_{φ} (x) = \infty$ when $φ$ never outputs $x$ .

Read $φ$ as "the programming language": $p$ is source code, $φ (p)$ is what it prints. Nothing so far is canonical — a language with a one-byte instruction for "print the Bible" makes the Bible trivially simple. The content of the subject begins with the observation that this freedom is bounded.

Theorem 15.2 (Invariance theorem). There is a description method $U$ — any universal one — such that for every description method $φ$ there is a constant $c_{φ}$ , depending on $φ$ but not on $x$ , with

C_{U} (x) \leq C_{φ} (x) + c_{φ} for every x .

Consequently, if $U$ and $V$ are both universal then $∣ C_{U} (x) - C_{V} (x) ∣ \leq c_{U, V}$ for all $x$ .

Proof. Enumerate the description methods as $φ_{1}, φ_{2}, \dots$ — the standard effective enumeration of partial computable functions. Encode the index $i$ self-delimitingly as $\overset{}{ˉ} = 1^{i} 0$ , and define

U (\overset{}{ˉ} p) = φ_{i} (p) .

$U$ is partial computable: it reads $1$ s until the first $0$ , recovers $i$ , and simulates $φ_{i}$ on the remainder. The prefix $1^{i} 0$ is uniquely readable, so $U$ is well defined.

Now take any $φ = φ_{i}$ and any $x$ with $C_{φ} (x) = ∣ p ∣ < \infty$ . Then $U (\overset{}{ˉ} p) = x$ , so $C_{U} (x) \leq ∣ \overset{}{ˉ} p ∣ = ∣ p ∣ + i + 1 = C_{φ} (x) + (i + 1)$ . Set $c_{φ} = i + 1$ , which depends only on the index of $φ$ .

For the second claim, apply the first with $φ = V$ to get $C_{U} (x) \leq C_{V} (x) + c_{V}$ , and again with the roles exchanged to get $C_{V} (x) \leq C_{U} (x) + c_{U}$ . Take $c_{U, V} = max (c_{U}, c_{V})$ .∎

Notation. Fix one universal $U$ once and for all and write $C (x)$ for $C_{U} (x)$ , the plain Kolmogorov complexity of $x$ . Every statement in this chapter has the form " $\dots + O (1)$ " or " $\dots + O (lo g n)$ ", and the invariance theorem is exactly what makes such statements independent of that fixed choice.

Pitfall. The constant is uniform in $x$ , not small. For any fixed string $y$ — say a gigabyte of video — there is a universal machine on which $C (y) = 1$ . So " $C (y) = 12$ " is a statement about a machine, not about $y$ . Only asymptotic statements about infinite families of strings, or comparisons where the same constant appears on both sides, carry machine-independent content.

Two easy upper bounds fix the scale.

Proposition 15.3 (The literal bound). There is a constant $c$ with $C (x) \leq ∣ x ∣ + c$ for every $x$ .

Proof. Let $φ (p) = p$ , the identity, which is computable. Then $C_{φ} (x) = ∣ x ∣$ , and the invariance theorem gives $C (x) \leq ∣ x ∣ + c_{φ}$ . The constant is the cost of saying "what follows is literal".∎

So no string is harder to describe than to write out; the interesting strings are the ones that are much easier.

Why plain complexity is not the last word

Plain complexity has a defect that shows up as soon as descriptions are combined. If $p$ describes $x$ and $q$ describes $y$ , the concatenation $pq$ does not describe the pair $(x, y)$ , because $U$ cannot tell where $p$ stops. Paying to mark the split is what produces the stray logarithms in the theory of $C$ , and — as we will see in Martin-Löf Randomness for Infinite Sequences — it also breaks $C$ irreparably as a randomness test for infinite sequences.

The repair is to require the descriptions themselves to be self-delimiting.

Definition 15.4 (Prefix-free machine and prefix complexity). A set $S \subseteq {0, 1}^{*}$ is prefix-free if no element of $S$ is a proper prefix of another. A machine $M$ is a prefix machine when its domain is prefix-free. Fixing a universal prefix machine $U$ , the prefix complexity of $x$ is

K (x) = min {∣ p ∣ : U (p) = x} .

The invariance theorem holds verbatim for prefix machines — the proof above goes through once one notes that the index $\overset{}{ˉ} = 1^{i} 0$ is prefix-free and that the simulated domains are prefix-free — so $K$ too is well defined up to $O (1)$ .

The reason to pay for self-delimitation is that it buys a probability measure, through the following classical inequality.

Theorem 15.5 (Kraft inequality). If $S \subseteq {0, 1}^{*}$ is prefix-free, then

p \in S \sum 2^{- ∣ p ∣} \leq 1.

In particular $\sum_{x} 2^{- K (x)} \leq 1$ , since the shortest programs for distinct strings are distinct elements of the prefix-free domain of $U$ .

Proof. Map each $p \in S$ to the half-open interval $I_{p} = [0. p, 0. p + 2^{- ∣ p ∣}) \subseteq [0, 1)$ , where $0. p$ is the binary fraction with digits $p$ . The interval $I_{p}$ consists of exactly those reals whose binary expansion begins with $p$ , so its length is $2^{- ∣ p ∣}$ .

If neither of $p, q$ is a prefix of the other, they first differ at some position $j \leq min (∣ p ∣, ∣ q ∣)$ , and no real can begin with both; hence $I_{p} \cap I_{q} = \emptyset$ . Prefix-freeness therefore makes ${I_{p}}_{p \in S}$ a family of pairwise disjoint subintervals of $[0, 1)$ , and the sum of their lengths is at most the length of $[0, 1)$ , which is $1$ .∎

Kraft's inequality says that $2^{- K (\cdot)}$ is a sub-probability distribution over strings — the seed of the whole probabilistic side of the theory, taken up in Algorithmic Probability and the Coding Theorem.

The price of self-delimitation is a logarithm in the literal bound.

Proposition 15.6 (Literal bound for prefix complexity). $K (x) \leq ∣ x ∣ + 2 lo g_{2} ∣ x ∣ + O (1)$ , and more generally $K (x) \leq C (x) + 2 lo g_{2} C (x) + O (1)$ . In the other direction $C (x) \leq K (x) + O (1)$ .

Proof. For a number $n$ written in binary as $b_{1} \dots b_{k}$ with $k = ⌊ lo g_{2} n ⌋ + 1$ , the string $\overset{n}{ˉ} = b_{1} b_{1} b_{2} b_{2} \dots b_{k} b_{k} 01$ is a self-delimiting encoding of $n$ of length $2 k + 2 = 2 lo g_{2} n + O (1)$ : a decoder reads digit pairs until it meets the unequal pair $01$ . Feed the prefix machine $\overline{∣ x ∣} x$ ; it recovers $∣ x ∣$ , then reads exactly that many further bits, so its domain is prefix-free, and the invariance theorem for prefix machines gives the first bound. Replacing $x$ by a shortest plain program for $x$ , of length $C (x)$ , gives the second.

For the last inequality, a universal prefix machine is a description method, so $C (x) \leq C_{U} (x) + O (1) = K (x) + O (1)$ by the plain invariance theorem.∎

Figure 15.7. The two literal bounds. Prefix complexity pays

2 lo g_{2} n

extra bits to make its programs self-delimiting, so the shaded gap between

n

and

n + 2 lo g_{2} n

is the entire price of self-delimitation — negligible beside

n

itself, which is why the results of this chapter are insensitive to the choice between

C

and

K

Intuition. $C (x)$ is the size of the smallest zip file of $x$ — counting the unzipper as free, since it is the same for everybody. A megabyte of zeros zips to almost nothing; a megabyte from a radioactive-decay source does not zip at all. Kolmogorov complexity is the idealisation of that experiment in which the compressor is allowed to be any program whatsoever, not just the tricks someone happened to ship.

Example 15.8 (Two strings of the same length). Let $z = 0^{1 0^{6}}$ and let $r$ be a string of $1 0^{6}$ bits produced by fair coin flips. Bound $C (z)$ and estimate $C (r)$ .

Solution. For $z$ : the program "print $0$ exactly $N$ times", with $N = 1 0^{6}$ hard-coded, consists of a fixed loop plus the binary numeral for $N$ . The numeral costs $⌈ lo g_{2} 1 0^{6} ⌉ = 20$ bits, so $C (z) \leq 20 + O (1)$ . Going to $1 0^{9}$ zeros raises this only to $30 + O (1)$ : $C (0^{n})$ grows like $lo g_{2} n$ .

For $r$ : the literal bound gives $C (r) \leq 1 0^{6} + O (1)$ . In the other direction, Most strings are incompressible shows that fewer than $2^{1 0^{6} - 20}$ strings of this length have complexity below $1 0^{6} - 20$ , so a coin-flipped $r$ lands in that set with probability under $2^{- 20} < 1 0^{- 6}$ . With overwhelming probability $C (r) = 1 0^{6} \pm O (1)$ .

The two lengths are equal and the two complexities differ by a factor of about $50000$ . That is the point of $C$ : it measures structure, not size.□

Example 15.9 (A string that looks random and is not). Let $s$ be the first $1 0^{4}$ binary digits of $π$ . Bound $C (s)$ .

Solution. A spigot algorithm computes the digits of $π$ from scratch; let $c_{π}$ be the length of a program implementing it. The program "run the spigot, print the first $N$ binary digits", with $N = 1 0^{4}$ hard-coded, gives

C (s) \leq c_{π} + ⌈ lo g_{2} 1 0^{4} ⌉ + O (1) = c_{π} + 14 + O (1) .

Writing the digits literally costs $1 0^{4}$ bits. Asking instead for the first million digits changes the bound by six bits, from $14$ to $20$ , while the literal cost rises to $1 0^{6}$ . So $C (π_{1 : N}) = O (lo g N)$ : the digits of $π$ pass every statistical test anyone has run on them and are nonetheless among the least complex strings of their length.□

Remark. That example is the standard warning against reading "algorithmically random" as "looks random". It also explains why $C$ is not a repackaging of statistical randomness testing: $C$ sees the generating program, while a statistical test sees only the sample.

Exercises for §15.1 →

15.2Algorithmic Probability and the Coding Theorem

Kraft's inequality showed that $2^{- K (x)}$ behaves like a probability. This section turns that observation into a definition, proves the resulting distribution is universal among computable ones, and then proves the theorem that closes the circle: the universal distribution and the shortest program are, to within a constant, the same object.

Imagine feeding the universal prefix machine $U$ a stream of fair coin flips. Because $U$ 's domain is prefix-free, $U$ knows when to stop reading; the probability that it reads exactly the bits of a given program $p$ and halts is $2^{- ∣ p ∣}$ . The chance that this experiment prints $x$ is the sum over all programs that print $x$ .

Definition 15.10 (Algorithmic probability). The algorithmic probability, or universal a priori probability, of a string $x$ is

m (x) = p : U (p) = x \sum 2^{- ∣ p ∣},

the sum being over the prefix-free domain of $U$ . By Kraft, $\sum_{x} m (x) \leq 1$ .

Notation. A function $μ : {0, 1}^{*} \to [0, 1]$ with $\sum_{x} μ (x) \leq 1$ is a discrete semimeasure; the inequality is strict for $m$ because $U$ may fail to halt. A semimeasure is lower semicomputable when some algorithm, given $x$ , emits a non-decreasing sequence of rationals converging to $μ (x)$ — it may never certify the value, but it never over-claims. $m$ is lower semicomputable: dovetail all programs and add $2^{- ∣ p ∣}$ each time one of them halts with output $x$ .

Theorem 15.11 (Universality of the algorithmic prior). For every lower semicomputable semimeasure $μ$ there is a constant $c_{μ} > 0$ , independent of $x$ , with

m (x) \geq c_{μ} \cdot μ (x) for all x,

and one may take $c_{μ} = 2^{- K (μ) - O (1)}$ , where $K (μ)$ is the prefix complexity of a program that lower-semicomputes $μ$ . In particular $m$ dominates every computable probability distribution.

Proof. Let $M_{μ}$ be a program of length $K (μ)$ that enumerates rationals increasing to $μ (x)$ for each $x$ . Build a prefix machine $N$ which, having read $M_{μ}$ , runs the following coding scheme.

Using the enumeration, construct a prefix-free code in which $x$ receives a codeword of length $⌈ lo g_{2} (1/ μ (x))⌉ + 1$ . Such a code exists and can be built effectively from below: this is the Shannon–Fano–Elias construction, which allocates to $x$ a dyadic subinterval of $[0, 1)$ of length $2^{- ⌈ l o g_{2} (1/ μ (x))⌉ - 1}$ inside the interval of mass $μ (x)$ that the enumeration is filling in. Disjointness of the allocated intervals follows from $\sum_{x} μ (x) \leq 1$ , and prefix-freeness from disjointness as in Kraft inequality. Let $N$ , on a codeword $w$ , output the $x$ that $w$ encodes.

Then $C_{N} (x) \leq lo g_{2} (1/ μ (x)) + 2$ , and simulating $N$ on $U$ costs the description of $N$ , which is $M_{μ}$ plus a constant. Hence

K (x) \leq lo g_{2} \frac{1}{μ ( x )} + K (μ) + O (1),

and since $m (x) \geq 2^{- K (x)}$ — the shortest program is one term of the sum — we get $m (x) \geq 2^{- K (μ) - O (1)} μ (x)$ .∎

The inequality is why $m$ deserves the name a priori. Whatever computable law $μ$ actually governs the data, $m$ has already given $μ$ a fixed positive share of its mass; no amount of data can drive that share to zero, so a learner who starts from $m$ can never be dogmatically wrong about a computable world. The price is paid entirely in the constant $2^{- K (μ)}$ : complicated hypotheses start further behind, but never at zero. That is Occam's razor, derived rather than assumed.

The proof extracted $K (x) \leq lo g_{2} (1/ m (x)) + O (1)$ along the way. Levin's coding theorem says the converse holds too, and this is much less obvious: it says that the sum over all programs for $x$ is dominated, up to a constant factor, by its single largest term.

Theorem 15.12 (Coding theorem).

K (x) = lo g_{2} \frac{1}{m ( x )} + O (1) .

Proof. One direction is immediate: $m (x) \geq 2^{- K (x)}$ , because the shortest program contributes $2^{- K (x)}$ to the sum, so $lo g_{2} (1/ m (x)) \leq K (x)$ .

The other direction is the substantial one, and what follows is a sketch naming what it rests on. Apply Universality of the algorithmic prior with $μ = m$ itself — legitimate because $m$ is a lower semicomputable semimeasure, which is why that theorem was stated for semimeasures rather than only for computable distributions. The construction inside its proof builds, from the enumeration of $m$ from below, a prefix-free code assigning $x$ a codeword of length $⌈ lo g_{2} (1/ m (x))⌉ + 1$ ; running that decoder on $U$ costs a further constant, so

K (x) \leq lo g_{2} \frac{1}{m ( x )} + O (1) .

The delicate point, which we do not carry out here, is that the code must be built on-line as the approximations to $m (x)$ increase, reallocating intervals as they grow. Li and Vitányi give that bookkeeping in full.∎

Intuition. The coding theorem says that if a string has many different short descriptions, then it also has one very short one. The mass $m (x)$ could in principle be spread thinly over billions of mediocre programs; the theorem says it cannot be. Algorithmic probability and description length are two views of one quantity: $m (x) \approx 2^{- K (x)}$ .

Example 15.13 (Weighing two hypotheses). Two programs are in play. $A$ = "always print H" has length $ℓ_{A} = 4$ ; $B$ = "print independent fair coin flips" has length $ℓ_{B} = 6$ . Using $2^{- ℓ}$ as the prior, compute the posterior after observing $x = H^{n}$ and the predicted probability that the next symbol is H, for $n = 3$ and $n = 10$ .

Solution. Priors: $w_{A} = 2^{- 4} = 1/16$ and $w_{B} = 2^{- 6} = 1/64$ . Likelihoods: $P (x ∣ A) = 1$ and $P (x ∣ B) = 2^{- n}$ .

Unnormalised posteriors: $A$ gets $1/16$ , $B$ gets $2^{- n} /64$ . For $n = 3$ these are $0.0625$ and $1/512 \approx 0.00195$ , so $P (A ∣ x) \approx 0.970$ and

P (next = H) \approx 0.970 \cdot 1 + 0.030 \cdot \frac{1}{2} \approx 0.985.

For $n = 10$ : $B$ gets $2^{- 10} /64 = 1/65 536 \approx 1.53 \times 1 0^{- 5}$ against $A$ 's $0.0625$ , so $P (A ∣ x) \approx 0.99976$ and $P (next = H) \approx 0.99988$ .

The prediction always lies strictly between $\frac{1}{2}$ and $1$ and climbs toward $1$ at rate $2^{- n}$ . Note what does the work: not the prior ratio $w_{A} / w_{B} = 4$ , a fixed handicap, but the likelihood ratio $2^{n}$ , which grows without bound. The prior only decides how much data is needed to overcome it — exactly the role $2^{- K (μ)}$ plays in Universality of the algorithmic prior.□

Pitfall. $m$ is a semimeasure, not a measure: $\sum_{x} m (x) < 1$ strictly, because the missing mass belongs to programs that never halt. Normalising $m$ to sum to $1$ destroys lower semicomputability, since you would have to know the deficiency — which is $1 - Ω$ , and $Ω$ is uncomputable. Working with semimeasures is not fastidiousness; it is forced.

Exercises for §15.2 →

15.3Chaitin's $Ω$ and the Limits of Proof

The mass that goes missing from Kraft's inequality because programs fail to halt is itself a number, and it turns out to be one of the more remarkable constants in mathematics.

Definition 15.14 (Chaitin's constant). For the fixed universal prefix machine $U$ ,

Ω = p : U (p) halts \sum 2^{- ∣ p ∣},

the sum over all $p$ on which $U$ halts. Equivalently, $Ω$ is the probability that $U$ halts when fed fair coin flips.

Proposition 15.15 (Omega is a real in the unit interval, approximable from below). $0 < Ω < 1$ , and there is an algorithm producing a non-decreasing computable sequence of rationals $Ω_{1} \leq Ω_{2} \leq \dots$ with $Ω_{t} \to Ω$ .

Proof. The domain of $U$ is prefix-free, so Kraft gives $Ω \leq 1$ , and $Ω > 0$ because $U$ halts on at least one program. For strictness, some program runs forever — for instance one searching for a proof of a false statement — and its interval, of positive length, is then disjoint from every counted interval, so $Ω \leq 1 - 2^{- ∣ p ∣} < 1$ .

For the approximation, let

Ω_{t} = \sum {2^{- ∣ p ∣} : ∣ p ∣ \leq t and U (p) halts within t steps} .

Each $Ω_{t}$ is a finite sum of dyadic rationals, computable by simulation; the sequence is non-decreasing because the qualifying set grows with $t$ ; and it converges to $Ω$ because every halting $p$ enters at some finite stage.∎

The approximation converges but gives no rate: at no stage do you know how much mass the still-running programs will eventually contribute. That is precisely the obstruction, and the next theorem turns it into a quantitative statement.

Theorem 15.16 (The first n bits of Omega decide the halting problem). From the first $n$ bits of the binary expansion of $Ω$ one can compute, for every program $p$ with $∣ p ∣ \leq n$ , whether $U (p)$ halts.

Proof. Write $Ω_{1 : n}$ for the number given by the first $n$ binary digits, so that $Ω_{1 : n} \leq Ω < Ω_{1 : n} + 2^{- n}$ . Run the approximation of Omega is a real in the unit interval, approximable from below until $Ω_{t} \geq Ω_{1 : n}$ ; this happens at some finite stage $t_{0}$ , since $Ω_{t} \to Ω \geq Ω_{1 : n}$ .

Claim. Every program of length at most $n$ that halts at all has already halted by stage $t_{0}$ . Suppose some $p$ with $∣ p ∣ \leq n$ halts later. Then the total halting mass is at least the already-counted $Ω_{t} \geq Ω_{1 : n}$ plus the not-yet-counted $2^{- ∣ p ∣} \geq 2^{- n}$ , giving $Ω \geq Ω_{1 : n} + 2^{- n}$ and contradicting the displayed bound.

So simulating every program of length $\leq n$ for $t_{0}$ steps decides halting for all of them.∎

Corollary 15.17 (Omega is uncomputable and incompressible). $Ω$ is not a computable real, and there is a constant $c$ with $K (Ω_{1 : n}) \geq n - c$ for every $n$ .

Proof. If $Ω$ were computable, The first n bits of Omega decide the halting problem would make the halting problem decidable, contradicting Turing's theorem.

For the second claim, from $Ω_{1 : n}$ we can compute the set of halting programs of length $\leq n$ , hence the finite set $S_{n}$ of their outputs; let $y_{n}$ be the first string not in $S_{n}$ . Every string of complexity $\leq n$ is in $S_{n}$ , so $K (y_{n}) > n$ . This exhibits a program that, given $Ω_{1 : n}$ , prints a string of complexity exceeding $n$ , so $n < K (y_{n}) \leq K (Ω_{1 : n}) + O (1)$ , where the constant is the length of that fixed program. Hence $K (Ω_{1 : n}) \geq n - c$ .∎

By the Levin–Schnorr theorem, proved in Martin-Löf Randomness for Infinite Sequences, that last inequality says exactly that the binary expansion of $Ω$ is a Martin-Löf random sequence. So $Ω$ is simultaneously random and meaningful: it encodes the halting problem, and it is lower semicomputable, which no "typical" real is.

Figure 15.18. Approximating

Ω

from below. Each halting program adds its

2^{- ∣ p ∣}

to the running total, so the staircase is non-decreasing and converges to

Ω

— but from the staircase alone you can never tell whether the next step is one stage away or a thousand, which is exactly the content of the halting problem.

$Ω$ now supplies the sharpest available statement of the limits of formal reasoning. The classical Gödel sentence is a single artificial statement; Chaitin's theorem says instead that an entire infinite family of perfectly concrete true statements lies beyond any fixed system, and it names the family.

Theorem 15.19 (Chaitin's incompleteness theorem). Let $F$ be a consistent, effectively axiomatised formal system strong enough to express statements of the form " $K (x) > k$ " and sound for them. Then there is a constant $c_{F}$ , of the order of the length of a program enumerating $F$ 's theorems, such that $F$ proves no statement " $K (x) > c_{F}$ ", for any string $x$ — even though all but finitely many strings satisfy $K (x) > c_{F}$ .

Proof. Consider the program $P_{k}$ which, with the number $k$ built in, enumerates all proofs of $F$ in order and halts, printing $x$ , as soon as it finds a proof of a statement " $K (x) > k$ " for some string $x$ .

Encode $k$ self-delimitingly, so that $∣ P_{k} ∣ \leq 2 lo g_{2} k + d$ , where the constant $d$ covers the proof enumerator for $F$ and the fixed control logic. If $P_{k}$ halts with output $x$ , then $x$ has a description of length $∣ P_{k} ∣$ , so

K (x) \leq 2 lo g_{2} k + d .

But $F$ proved " $K (x) > k$ ", and $F$ is sound for such statements, so $K (x) > k$ . Combining,

k < K (x) \leq 2 lo g_{2} k + d .

Since $k$ eventually outgrows $2 lo g_{2} k + d$ , this is false for all large $k$ . Fix $c_{F}$ to be any such $k$ . For that $c_{F}$ the program $P_{c_{F}}$ can never halt, which says exactly that $F$ proves no statement " $K (x) > c_{F}$ ".

For the final clause, Most strings are incompressible gives that at most $2^{c_{F}} - 1$ strings have $K (x) \leq c_{F}$ .∎

Intuition. A formal system cannot certify randomness far beyond its own description length. If it could, it would be pulling complexity out of thin air: the axioms plus a few bits of search would produce an object provably more complex than the axioms themselves. Chaitin's theorem is the information-theoretic form of "you cannot get more out than you put in".

Example 15.20 (Where the constant sits for a real system). Roughly how large is $c_{F}$ for a system like ZFC, and what does the theorem forbid in practice?

Solution. The constant is essentially the length of a program that enumerates the theorems of ZFC — the axiom schemas, a proof checker, and the search loop. Written compactly that is on the order of a few thousand bits, and the exact figure is machine-dependent by the invariance theorem.

What is forbidden: ZFC cannot prove, of any specific string $x$ , that $K (x) > 1 0^{6}$ , even though almost every million-bit string satisfies it, and even though ZFC readily proves the counting statement "all but a $2^{- 20}$ fraction of million-bit strings have $K > 1 0^{6} - 20$ ". The existence claim is provable; no instance of it is. This is the cleanest known example of a theory proving $\exists x Φ (x)$ while proving $Φ (t)$ for no term $t$ .□

Pitfall. " $Ω$ is random" does not mean its digits are arbitrary or patternless in the informal sense. They are highly meaningful — they encode the halting problem — and $Ω$ is lower semicomputable, so it is far from a typical real in any computational sense. Algorithmic randomness means "no program much shorter than $n$ outputs the first $n$ bits", nothing more and nothing less.

Exercises for §15.3 →

15.4Conditional and Joint Complexity

Everything so far measured the cost of describing $x$ from nothing. Shannon's theory becomes interesting only once it can condition — $H (X ∣ Y)$ , $I (X; Y)$ — and the algorithmic theory is the same. This section builds the relative version of $K$ and establishes the bounds that the chain rule of Properties of Kolmogorov Complexity will sharpen into equalities.

Notation. Fix a computable pairing bijection $⟨ \cdot, \cdot ⟩ : {0, 1}^{*} \times {0, 1}^{*} \to {0, 1}^{*}$ , for instance $⟨ x, y ⟩ = \overset{x}{ˉ} y$ with $\overset{x}{ˉ}$ the self-delimiting encoding of Literal bound for prefix complexity. Natural numbers are identified with binary strings through the standard order $ε, 0, 1, 00, 01, \dots$ , so $K (n)$ is meaningful for a number $n$ .

Definition 15.21 (Conditional and joint complexity). The conditional prefix complexity of $x$ given $y$ is

K (x ∣ y) = min {∣ p ∣ : U (⟨ y, p ⟩) = x},

the length of the shortest program that prints $x$ when $y$ is supplied free of charge on a separate input tape. The joint complexity of $x$ and $y$ is $K (x, y) = K (⟨ x, y ⟩)$ .

The convention that $y$ is free is what makes $K (\cdot ∣ y)$ a complexity in its own right: for each fixed $y$ the map $p \mapsto U (⟨ y, p ⟩)$ is a prefix machine, so an invariance theorem holds for it, with a constant that does not depend on $y$ .

Proposition 15.22 (Elementary bounds). For all strings $x, y$ , up to an additive constant independent of $x$ and $y$ :

K (x ∣ y) \leq K (x) + O (1), K (x) \leq K (x, y) + O (1),

K (x, y) \leq K (x) + K (y ∣ x) + O (1), K (x, y) \leq K (x) + K (y) + O (1) .

Proof. For the first: ignore $y$ and run a shortest unconditional program for $x$ ; the constant is the cost of the instruction "discard the side information".

For the second: from $⟨ x, y ⟩$ the pairing is computably invertible, so a shortest program for the pair followed by "take the first component" prints $x$ .

For the third — this is where prefix-freeness earns its keep. Let $p$ be a shortest program for $x$ and $q$ a shortest program for $y$ given $x$ . Feed the machine $pq$ . Because the domain of $U$ is prefix-free, $U$ reading $pq$ consumes exactly $p$ , halts with $x$ , and control can then be handed to a second phase which reads exactly $q$ from the remaining bits and, with $x$ in hand, prints $y$ . The composite machine has prefix-free domain and prints $⟨ x, y ⟩$ from $∣ p ∣ + ∣ q ∣$ bits. With plain complexity this argument fails: $C$ cannot tell where $p$ ends, and one must pay an extra $O (lo g)$ to mark the boundary.

The fourth follows from the third with Elementary bounds' first inequality, $K (y ∣ x) \leq K (y) + O (1)$ .∎

Intuition. Subadditivity is the statement that describing two things together is never much worse than describing them separately, and is often much better: the shared structure is paid for once. The chain-rule inequality $K (x, y) \leq K (x) + K (y ∣ x)$ says the natural way to describe a pair is to describe the first, then describe the second in the context of the first — precisely the algorithmic mirror of $H (X, Y) = H (X) + H (Y ∣ X)$ .

There is a subtlety here with no counterpart in Shannon's theory, and it is the commonest source of confusion in the subject: conditioning on the length of a string is not free.

Proposition 15.23 (Complexity given the length). For every $x$ of length $n$ ,

K (x) \leq K (x ∣ n) + K (n) + O (1),

and the maximum of $K (x)$ over strings of length $n$ is $n + K (n) + O (1)$ , while the maximum of $K (x ∣ n)$ over the same strings is $n + O (1)$ .

Proof. The inequality is Elementary bounds applied to the pair $(n, x)$ : describe $n$ , then describe $x$ given $n$ .

For the second claim, the upper bound $K (x) \leq n + K (n) + O (1)$ comes from that inequality together with $K (x ∣ n) \leq n + O (1)$ : given $n$ , the program "read the next $n$ bits and print them" needs no self-delimiting length field. The matching lower bound — that some $x$ of length $n$ attains it — follows by counting, as in Most strings are incompressible: there are $2^{n}$ strings and fewer than $2^{n + K (n)}$ programs of length below $n + K (n)$ , but the counting must be carried out over the prefix-free domain, where the available programs of each length are limited by Kraft; Li and Vitányi carry out that refinement. We use only the upper bound below.∎

So for a typical $n$ -bit string $x$ ,

K (x) = n + K (n) + O (1) = n + lo g_{2} n + 2 lo g_{2} lo g_{2} n + O (1),

the extra term being the cost of announcing where the string ends. This is why statements about incompressibility come in two flavours, $K (x) \geq n - c$ and $K (x ∣ n) \geq n - c$ , and why the second is the technically convenient one.

Example 15.24 (Conditional complexity in three easy cases). Evaluate, to within an additive constant: (a) $K (x ∣ x)$ ; (b) $K (x, x)$ ; (c) $K (x ∣ x^{*})$ , where $x^{*}$ is a shortest program for $x$ .

Solution. (a) $K (x ∣ x) = O (1)$ : the program "print the side information" has fixed length, independent of $x$ .

(b) $K (x, x) = K (x) + O (1)$ . Upper bound: describe $x$ once and then apply the fixed computable map $z \mapsto ⟨ z, z ⟩$ . Lower bound: $K (x) \leq K (x, x) + O (1)$ by Elementary bounds. The chain rule then charges $K (x ∣ x^{*}) = O (1)$ for the second copy, exactly as $H (X, X) = H (X)$ charges nothing.

(c) $K (x ∣ x^{*}) = O (1)$ : run the program you were handed. Note that $K (x ∣ x^{*})$ can be genuinely smaller than $K (x ∣ x)$ is large — the point is the converse direction, that $K (x^{*} ∣ x)$ need not be $O (1)$ , since finding a shortest program for a string you already possess is an uncomputable search.□

Pitfall. Conditioning on $x$ and conditioning on $x^{*}$ are different, and the difference is not a constant: $K (x^{*} ∣ x)$ can be as large as $K (K (x)) \approx lo g lo g$ of the length. The chain rule of Properties of Kolmogorov Complexity is exact only in the $x^{*}$ form; in the $x$ form it carries an $O (lo g)$ error term. Papers that state it with $x$ and claim $O (1)$ are wrong.

Example 15.25 (A pair with shared structure). Let $x$ be an incompressible string of length $n$ , and let $y = \overset{x}{ˉ}$ be its bitwise complement. Compute $K (x, y)$ and $K (y ∣ x)$ to within $O (1)$ .

Solution. Complementation is a fixed computable involution, so $K (y ∣ x) = O (1)$ : "flip every bit of the side information". By the chain-rule inequality, $K (x, y) \leq K (x) + O (1)$ , and by Elementary bounds, $K (x) \leq K (x, y) + O (1)$ , so $K (x, y) = K (x) + O (1) = n + K (n) + O (1)$ .

Contrast the naive count: $x$ and $y$ are each incompressible, each about $n$ bits, and yet the pair costs $n$ rather than $2 n$ . Incompressibility of the parts says nothing about incompressibility of the pair, because "random" is not the same as "independent". Two independent incompressible strings, as computed in Properties of Kolmogorov Complexity, do cost $2 n$ .□

Exercises for §15.4 →

15.5The Average of K is the Entropy

Kolmogorov complexity was built without any probability in sight, and Shannon entropy cannot even be evaluated without a distribution. The two are nevertheless the same quantity in the only sense in which they could be: average $K$ over a computable source and you recover $H$ , up to a constant that pays for describing the source.

Throughout this section $P$ is a computable probability distribution on ${0, 1}^{*}$ with finite entropy $H (P) = - \sum_{x} P (x) lo g_{2} P (x)$ , and $K (P)$ denotes the prefix complexity of a program computing $P$ .

Theorem 15.26 (Expected complexity equals entropy). For every computable probability distribution $P$ ,

H (P) \leq x \sum P (x) K (x) \leq H (P) + K (P) + O (1),

with an $O (1)$ that depends on neither $P$ nor $x$ . In particular $E [K (X)] = H (X) + O (1)$ for any fixed source, and the constant is negligible against $H$ for a long sequence.

Proof. Upper bound. Universality of the algorithmic prior, applied to $μ = P$ , gave $K (x) \leq lo g_{2} (1/ P (x)) + K (P) + O (1)$ for every $x$ . Multiply by $P (x)$ and sum:

x \sum P (x) K (x) \leq x \sum P (x) lo g_{2} \frac{1}{P ( x )} + K (P) + O (1) = H (P) + K (P) + O (1) .

Lower bound. The shortest programs for distinct strings are distinct elements of the prefix-free domain of $U$ , so by Kraft inequality the numbers $q (x) = 2^{- K (x)}$ satisfy $S = \sum_{x} q (x) \leq 1$ . Let $Q (x) = q (x) / S$ , a genuine probability distribution. Since $K (x) = lo g_{2} (1/ q (x))$ ,

x \sum P (x) K (x) - H (P) = x \sum P (x) lo g_{2} \frac{P ( x )}{q ( x )} = x \sum P (x) lo g_{2} \frac{P ( x )}{Q ( x )} - lo g_{2} S = D (P ∥ Q) - lo g_{2} S .

Both terms are non-negative: $D (P ∥ Q) \geq 0$ by Gibbs' inequality, and $- lo g_{2} S \geq 0$ because $S \leq 1$ . This is Shannon's noiseless coding lower bound, applied to the code whose length function is $K$ .∎

The two bounds say that $K$ is an optimal code length for every computable source at once, paying only the fixed overhead $K (P)$ of naming the source — no code designed for a single $P$ can do better on that $P$ , and $K$ matches all of them simultaneously. That is the algorithmic form of universal compression.

The averaged statement conceals a sharper pointwise one: not merely the mean of $K$ but $K$ itself tracks the self-information $- lo g_{2} P (x)$ , on all but an exponentially small set.

Theorem 15.27 (K equals self-information with high probability). For every computable $P$ and every $k \geq 0$ ,

P {x : K (x) < lo g_{2} \frac{1}{P ( x )} - k} \leq 2^{- k},

while $K (x) \leq lo g_{2} \frac{1}{P ( x )} + K (P) + O (1)$ holds for every $x$ . Hence with probability at least $1 - 2^{- k}$ ,

lo g_{2} \frac{1}{P ( x )} - k \leq K (x) \leq lo g_{2} \frac{1}{P ( x )} + K (P) + O (1) .

Proof. Let $A$ be the set in the display. For $x \in A$ the condition $K (x) < lo g_{2} (1/ P (x)) - k$ rearranges to $P (x) < 2^{- K (x) - k}$ . Summing over $A$ and using Kraft inequality,

P (A) = x \in A \sum P (x) < 2^{- k} x \in A \sum 2^{- K (x)} \leq 2^{- k} .

The upper bound is the inequality already proved in Universality of the algorithmic prior. Intersecting the two events gives the final display.∎

Intuition. A source emits its typical strings with probability about $2^{- H}$ each, and there are about $2^{H}$ of them. Indexing that list costs $H$ bits, and no shorter description exists for most of the list because there is no room — $2^{H}$ objects need $H$ -bit names. $K$ discovers this indexing on its own, without being told $P$ ; the only thing it has to be told, at cost $K (P)$ , is which list to use.

Example 15.28 (A biased source). A source emits $1000$ independent bits, each a $1$ with probability $0.2$ . Estimate $E [K (X^{1000})]$ , and bound the probability that a particular emitted string has $K$ at least $20$ bits below its self-information.

Solution. The binary entropy at $p = 0.2$ is

h_{2} (0.2) = - 0.2 lo g_{2} 0.2 - 0.8 lo g_{2} 0.8 = 0.2 (2.3219) + 0.8 (0.3219) = 0.7219 bits.

For $n$ independent bits, $H (X^{n}) = n h_{2} (p) = 721.9$ bits, so Expected complexity equals entropy gives $E [K (X^{1000})] = 722 + O (1)$ bits — a compression to $72%$ of the literal $1000$ bits, and the $O (1)$ here is the few dozen bits needed to write down "independent bits with $p = 1/5$ ".

For the tail, K equals self-information with high probability with $k = 20$ gives probability at most $2^{- 20} \approx 9.5 \times 1 0^{- 7}$ . Note what this does not say: it does not say the string is close to $722$ bits, only close to its own $- lo g_{2} P (x)$ , which varies from string to string. Averaging that variation is what produces $H$ .□

Pitfall. $K (x) \approx - lo g_{2} P (x)$ is a statement about $P$ -random draws, not about strings you chose. Choose $x = 0^{1000}$ from the source above: its self-information is $- lo g_{2} (0. 8^{1000}) = 321.9$ bits, but $K (x) = O (lo g n)$ , roughly $20$ bits. No contradiction — $0^{1000}$ sits in the exceptional set, which has probability $0. 8^{1000} \approx 1 0^{- 97}$ .

Remark. The analogy is close but not perfect, and the imperfections are instructive. $H$ is always non-negative and $K$ is always positive; $H (X ∣ Y) \leq H (X)$ always, but $K (x ∣ y) \leq K (x) + O (1)$ only up to the constant — there are $x, y$ with $K (x ∣ y) > K (x)$ , since a misleading $y$ can be worse than no $y$ at all as long as the excess stays inside the constant. And $H$ is a function of the distribution while $K$ is a function of the outcome: no amount of averaging can recover the individual-object information that $K$ carries.

Exercises for §15.5 →

15.6Most Strings Are Incompressible

That some strings are incompressible follows from an argument so short it can be stated in one line: there are more strings than short programs. What makes the observation powerful is that it can be run backwards, and that is the incompressibility method — a counting technique that proves theorems having nothing to do with computability.

Theorem 15.29 (Most strings are incompressible). For every $k$ , the number of strings $x$ with $C (x) < k$ is at most $2^{k} - 1$ . Consequently, for every $n$ and every $c \geq 0$ , the number of strings of length $n$ with $C (x) < n - c$ is fewer than $2^{n - c}$ , so the fraction of $n$ -bit strings with

C (x) \geq n - c

exceeds $1 - 2^{- c}$ , a bound that does not depend on $n$ .

Proof. A string with $C (x) < k$ has a program of length $0, 1, \dots, k - 1$ , and there are $2^{0} + 2^{1} + \dots + 2^{k - 1} = 2^{k} - 1$ such strings of bits in total. Each program, being deterministic, outputs at most one string, so at most $2^{k} - 1$ distinct strings receive one.

Apply this with $k = n - c$ : fewer than $2^{n - c}$ strings of any length, hence in particular of length $n$ , have $C (x) < n - c$ . There are exactly $2^{n}$ strings of length $n$ , so the compressible fraction is below $2^{n - c} / 2^{n} = 2^{- c}$ .∎

Definition 15.30 (Incompressible string). A string $x$ is $c$ -incompressible if $C (x) \geq ∣ x ∣ - c$ , and incompressible if $c$ is taken to be $0$ , so that $C (x) \geq ∣ x ∣$ . The same definitions are used with $K (\cdot)$ or $K (\cdot ∣ n)$ in place of $C$ ; the three notions differ by $O (lo g n)$ in the constant, which is immaterial for the applications below.

Corollary 15.31 (Incompressible strings of every length exist). For every $n$ there is a string of length $n$ with $C (x) \geq n$ .

Proof. Take $c = 0$ in Most strings are incompressible: fewer than $2^{n}$ strings of length $n$ have $C (x) < n$ , and there are $2^{n}$ of them, so at least one is left over.∎

Intuition. Short descriptions are a scarce resource: there are only about $2^{n - c}$ of them below length $n - c$ , and $2^{n}$ strings competing for them. The pigeonhole principle does the rest. Everything difficult in this chapter comes from the fact that we cannot point to the incompressible strings, only count them.

Method 15.32 (The incompressibility method). To prove that some property $Φ$ holds of almost all objects of size $n$ :

Fix a string $x$ of length $n$ with $C (x) \geq n - c$ ; such $x$ exist in abundance by Most strings are incompressible.
Assume $Φ$ fails for the object encoded by $x$ .
Use the failure of $Φ$ as a regularity: build a description of $x$ that exploits it.
If that description is shorter than $n - c$ , the assumption contradicts incompressibility, so $Φ$ holds.

The method replaces an averaging argument over a probability space by a single, arbitrary, typical object — which is why proofs by incompressibility are usually shorter than the probabilistic proofs they replace.

Example 15.33 (Chaitin's proof that there are infinitely many primes). Use incompressibility to show the set of primes is infinite.

Solution. Suppose there were only finitely many primes, $p_{1} < \dots < p_{k}$ . Every positive integer $n$ then factors as $n = p_{1}^{e_{1}} \dots p_{k}^{e_{k}}$ , and each exponent satisfies $e_{i} \leq lo g_{2} n$ , so $e_{i}$ fits in $lo g_{2} lo g_{2} n + O (1)$ bits.

This gives a description of $n$ : the list of $k$ exponents, each self-delimited, for a total of

C (n) \leq k \cdot (2 lo g_{2} lo g_{2} n + O (1)) = O (lo g lo g n) .

But by Most strings are incompressible there are integers $n$ of every bit-length $ℓ$ with $C (n) \geq ℓ - 1 \approx lo g_{2} n$ . For large $n$ , $lo g_{2} n$ exceeds $O (lo g lo g n)$ , a contradiction. Hence no finite list of primes suffices.

The whole of the number theory used is the fundamental theorem of arithmetic; the counting is done by the complexity bound.□

Theorem 15.34 (Incompressible strings are statistically balanced). Let $x$ have length $n$ and exactly $k$ ones, and suppose $C (x) \geq n - c$ . Then

\frac{k}{n} - \frac{1}{2} \leq \frac{( ln 2 ) ( c + 2 lo g _{2} n + O ( 1 ))}{2 n},

so the number of ones is $n /2 + O (n (c + lo g n))$ .

Proof. Describe $x$ by giving $n$ , then $k$ , then the index of $x$ in the lexicographic list of the $(k n)$ strings of length $n$ with $k$ ones. Encoding $n$ and $k$ self-delimitingly costs $2 lo g_{2} n + O (1)$ bits each; the index costs $⌈ lo g_{2} (k n) ⌉$ bits. A fixed program reconstructs $x$ from these, so

C (x) \leq lo g_{2} (k n) + 2 lo g_{2} n + O (1),

absorbing the two length fields into the single $2 lo g_{2} n + O (1)$ term with a larger constant. The standard entropy bound $(k n) \leq 2^{n h_{2} (k / n)}$ , with $h$ the binary entropy, gives $C (x) \leq n h_{2} (k / n) + 2 lo g_{2} n + O (1)$ .

Combine with the hypothesis $C (x) \geq n - c$ :

n - c \leq n h_{2} (k / n) + 2 lo g_{2} n + O (1) ⟹ 1 - h_{2} (k / n) \leq \frac{c + 2 lo g _{2} n + O ( 1 )}{n} .

Finally, writing $k / n = \frac{1}{2} + δ$ , the inequality $h_{2} (\frac{1}{2} + δ) \leq 1 - \frac{2 δ ^{2}}{l n 2}$ turns this into $\frac{2 δ ^{2}}{l n 2} \leq \frac{c + 2 l o g _{2} n + O ( 1 )}{n}$ , which is the claim.∎

Example 15.35 (How balanced, concretely). Take $n = 1 0^{6}$ and $c = 100$ . How far from $500000$ ones can a $c$ -incompressible string be?

Solution. Here $2 lo g_{2} 1 0^{6} = 39.9$ , so the numerator is $c + 2 lo g_{2} n + O (1) \approx 140$ . Then

δ \leq \frac{0.6931 \times 140}{2 \times 1 0 ^{6}} = 4.85 \times 1 0^{- 5} = 6.97 \times 1 0^{- 3},

so the count of ones lies in $500000 \pm 6970$ — a relative deviation under $1.4%$ . Compare the probabilistic statement: a fair-coin string of this length has its count within $\pm 5000$ of the mean with probability about $99.99%$ . The incompressibility bound is slightly weaker and completely deterministic: it holds of every string with $C (x) \geq n - 100$ , with no probability space anywhere in the argument.□

Pitfall. " $x$ is incompressible" is always relative to a slack $c$ , and the slack must be fixed before the argument, not chosen afterwards to make it work. A statement like "the string is incompressible, therefore it has no repeated block of length $lo g n$ " is only true for $c$ small compared with the saving the repetition would buy; spell out that comparison every time.

Remark. Nothing in this section says which strings are incompressible; Most strings are incompressible is a pure counting argument and produces no example. By Chaitin's incompleteness theorem no formal system can supply one either, beyond its own complexity. The incompressibility method finesses this: it never needs a named incompressible string, only the fact that one exists.

Exercises for §15.6 →

15.7The Uncomputability of K

The definition of $K$ quantifies over all programs, and so it is no surprise that $K$ is not computable. What is worth proving carefully is the shape of the failure: $K$ can be approached from one side and not the other, no computable function is an unbounded lower bound for it, and consequently the compressible strings are recognisable while the incompressible ones are not.

Theorem 15.36 (K is upper semicomputable). There is a total computable function $(x, t) \mapsto K^{t} (x)$ , non-increasing in $t$ , with $lim_{t \to \infty} K^{t} (x) = K (x)$ for every $x$ .

Proof. Define $K^{t} (x) = min {∣ p ∣ : ∣ p ∣ \leq t and U (p) = x within t steps}$ , with the convention $K^{t} (x) = ∣ x ∣ + 2 lo g_{2} ∣ x ∣ + c$ — the literal bound of Literal bound for prefix complexity — when the set is empty. Each $K^{t} (x)$ is computable by simulating finitely many programs for finitely many steps, and the minimum is over a set that only grows with $t$ , so the sequence is non-increasing.

It converges to $K (x)$ because a shortest program $p^{*}$ for $x$ halts after some finite number $t^{*}$ of steps, so $K^{t} (x) = K (x)$ for all $t \geq max (t^{*}, ∣ p^{*} ∣)$ , and it never drops below $K (x)$ since every candidate counted is a genuine program for $x$ .∎

What the proof does not supply is a stopping rule: at stage $t$ you hold an upper bound and no way to know whether it is the truth or whether some program still running will beat it in a billion steps. The next theorem shows that no cleverness repairs this.

Theorem 15.37 (K is not computable). There is no algorithm that halts on every input $x$ and outputs $K (x)$ .

Proof. Suppose $Kcomp$ is such an algorithm. For a number $m$ , let $Q_{m}$ be the program which, with $m$ built in, enumerates the strings $ε, 0, 1, 00, 01, \dots$ in lexicographic order, evaluates $Kcomp$ on each, and prints the first string $x_{m}$ with $Kcomp (x_{m}) \geq m$ .

Such an $x_{m}$ exists: by Most strings are incompressible only finitely many strings have complexity below $m$ , so the search terminates, and $Q_{m}$ therefore halts.

Encoding $m$ self-delimitingly, $∣ Q_{m} ∣ \leq 2 lo g_{2} m + d$ , where $d$ covers the enumerator and $Kcomp$ and does not depend on $m$ . Since $Q_{m}$ prints $x_{m}$ ,

K (x_{m}) \leq 2 lo g_{2} m + d .

But by construction $K (x_{m}) = Kcomp (x_{m}) \geq m$ , so $m \leq 2 lo g_{2} m + d$ . Choosing $m$ larger than $2 lo g_{2} m + d$ — possible, since $m$ outgrows $2 lo g_{2} m$ — contradicts this. Hence $Kcomp$ does not exist.∎

Intuition. This is the Berry paradox — "the least integer not describable in fewer than twenty syllables", a phrase of fewer than twenty syllables — turned from a joke into a theorem. The paradox is defused in ordinary language because "describable" is vague; fix a machine and it becomes precise, and what breaks instead is the assumption that complexity is computable.

Theorem 15.38 (No computable unbounded lower bound). If $f$ is a computable function with $f (x) \leq K (x)$ for all $x$ , then $f$ is bounded above.

Proof. Suppose $f$ is unbounded. Then for each $m$ the search for a string with $f (x) \geq m$ terminates, so the program $R_{m}$ that enumerates strings and prints the first $x$ with $f (x) \geq m$ halts, and $∣ R_{m} ∣ \leq 2 lo g_{2} m + d$ for a constant $d$ . Its output $x$ satisfies $m \leq f (x) \leq K (x) \leq 2 lo g_{2} m + d$ , false for large $m$ .∎

Corollary 15.39 (Incompressibility cannot be certified). The set ${x : K (x) \geq ∣ x ∣}$ contains no infinite computably enumerable subset, while its complement ${x : K (x) < ∣ x ∣}$ is computably enumerable.

Proof. The complement is enumerable by dovetailing: run all programs of length below $∣ x ∣$ and list each $x$ as soon as one of them prints it.

For the first claim, suppose $A$ were an infinite c.e. set of incompressible strings, enumerated as $a_{1}, a_{2}, \dots$ . Define $f (x) = max {∣ a_{i} ∣ : i \leq (index at which x appears)}$ — more simply, note that the program "print the first enumerated element of $A$ of length at least $m$ " has length $2 lo g_{2} m + d$ and outputs a string of complexity at least $m$ , which is the same contradiction as above.∎

So the situation is exactly one-sided: you can always discover that a string is compressible, by finding a short program, and you can never establish that it is not. Every practical compressor is a partial implementation of the enumerable half.

Example 15.40 (Why dovetailing does not terminate). You run all programs of length $\leq 50$ in parallel on a target $x$ of length $40$ . After a year, the shortest program that has printed $x$ has length $38$ . What may you conclude about $K (x)$ ?

Solution. Only that $K (x) \leq 38$ . The programs still running are the problem: one of length $12$ might halt tomorrow with output $x$ , and there is no computable bound on how long to wait — that bound would decide the halting problem for length- $12$ programs, which by The first n bits of Omega decide the halting problem is equivalent to knowing the first $12$ bits of $Ω$ .

Nor can you conclude $x$ is compressible in any useful sense: $38 < 40$ , but the literal bound already gives $K (x) \leq 40 + 2 lo g_{2} 40 + O (1)$ , so a saving of two bits is within the additive constant and carries no machine-independent content.□

Pitfall. "Uncomputable" is not "unknowable in every instance". $K (0^{n})$ is known to within $O (1)$ for every $n$ , and $K$ of any string you can generate by a short program is bounded above tightly. What fails is uniformity: no single algorithm works for all inputs, and lower bounds are unavailable except through counting arguments that name no string.

Exercises for §15.7 →

15.8Properties of Kolmogorov Complexity

The elementary inequalities of Conditional and Joint Complexity become equalities, and the theory acquires the full algebra of Shannon's information measures. The result at the centre is due to Kolmogorov and Levin, and it is the deepest fact in elementary algorithmic information theory.

Theorem 15.41 (Symmetry of information (Kolmogorov–Levin)). Up to an additive constant,

K (x, y) = K (x) + K (y ∣ x^{*}) + O (1),

where $x^{*}$ denotes a fixed shortest program for $x$ . Consequently

K (x) - K (x ∣ y^{*}) = K (y) - K (y ∣ x^{*}) + O (1) :

the information $y$ carries about $x$ equals the information $x$ carries about $y$ .

Proof. The inequality $\leq$ was proved in Elementary bounds, in the stronger form with $K (y ∣ x)$ ; since $K (y ∣ x^{*}) \leq K (y ∣ x) + O (1)$ fails in general but $x$ is computable from $x^{*}$ , the version with $x^{*}$ follows by running $x^{*}$ to obtain $x$ first.

The direction $\geq$ — that the pair cannot be described more cheaply than this two-stage scheme — is the substantial half, and we sketch it, naming what it rests on. Fix $x, y$ and put $k = K (x, y)$ . Consider the c.e. set $A = {(u, v) : K (u, v) \leq k}$ , which has at most $2^{k}$ elements by Most strings are incompressible. Let $m$ be the number of $v$ with $(x, v) \in A$ . Knowing $k$ and $m$ , one can enumerate $A$ until $m$ pairs with first component $x$ appear, and then index $y$ among them with $lo g_{2} m$ bits, giving $K (y ∣ x^{*}) \leq lo g_{2} m + O (lo g k)$ . Separately, the set of $u$ having at least $m$ partners in $A$ has at most $2^{k} / m$ members, and $x$ belongs to it, so $K (x) \leq k - lo g_{2} m + O (lo g k)$ . Adding the two gives $K (x) + K (y ∣ x^{*}) \leq k + O (lo g k)$ . Removing the logarithmic slack to reach $O (1)$ requires carrying $k$ and $m$ implicitly rather than explicitly, which is Levin's refinement; Li and Vitányi give it in full.

The symmetry statement follows by expanding $K (x, y)$ in both orders — $K (x, y) = K (y, x) + O (1)$ , since the pairing is computably reversible — and cancelling.∎

Definition 15.42 (Algorithmic mutual information).

I_{K} (x : y) = K (x) + K (y) - K (x, y) .

By symmetry of information, $I_{K} (x : y) = K (y) - K (y ∣ x^{*}) + O (1)$ , the number of bits that knowing $x$ saves when describing $y$ .

Intuition. Read the chain rule as an accounting identity. To buy the pair you first buy $x$ ; the receipt $x^{*}$ you are left holding is then legal tender toward $y$ . $I_{K} (x : y)$ is the discount. The Shannon identity $H (X, Y) = H (X) + H (Y ∣ X)$ is the same accounting averaged over an ensemble — and indeed, for a computable joint source, $E [I_{K} (x : y)] = I (X; Y) + O (1)$ by Expected complexity equals entropy applied three times.

Proposition 15.43 (Information is not increased by computation). For every partial computable $f$ and every $x$ in its domain,

K (f (x)) \leq K (x) + K (f) + O (1),

where $K (f)$ is the prefix complexity of a program for $f$ . In particular, for a fixed $f$ the increase is $O (1)$ , and for a computable bijection $K (f (x)) = K (x) + O (1)$ .

Proof. Concatenate a self-delimiting program for $f$ with a shortest program for $x$ ; the composite machine runs the second, applies the first, and prints $f (x)$ . Prefix-freeness makes the concatenation unambiguous, as in Elementary bounds. For a bijection, apply the bound to $f$ and to $f^{- 1}$ .∎

This is the algorithmic data-processing inequality, and it has a sharp moral: no amount of post-processing creates information. Running a pseudorandom generator on a $128$ -bit seed produces a gigabyte of output whose $K$ is at most $128 + K (generator) + O (1)$ bits, no matter how random the output looks.

Pitfall. Subadditivity holds only up to the constant, and the constant matters when you iterate. $K (x_{1} \dots x_{n}) \leq \sum_{i} K (x_{i}) + O (n)$ , not $\sum_{i} K (x_{i}) + O (1)$ : each concatenation pays again. Chains of inequalities in this subject must track how many times the constant is incurred, which is why results are stated with an explicit $O (\cdot)$ in the number of pieces.

Example 15.44 (Independent versus dependent pairs). Let $x$ and $y$ be independently drawn incompressible strings of length $n$ , and separately let $y^{'} = x$ . Compute $K (x, y)$ , $K (x, y^{'})$ and the corresponding $I_{K}$ .

Solution. For the independent pair: $K (x) = K (y) = n + K (n) + O (1)$ . Since $y$ shares no structure with $x$ , $K (y ∣ x^{*}) = K (y) + O (1)$ , and the chain rule gives

K (x, y) = K (x) + K (y) + O (1) \approx 2 n,

so $I_{K} (x : y) = O (1)$ . (A genuine proof that $K (y ∣ x^{*}) = K (y) + O (1)$ for some such pair is again a counting argument: fewer than $2^{n - c}$ strings $y$ have $K (y ∣ x^{*}) < n - c$ , for each fixed $x$ .)

For $y^{'} = x$ : $K (x, x) = K (x) + O (1) \approx n$ by Conditional complexity in three easy cases, so

I_{K} (x : x) = K (x) + K (x) - K (x, x) = K (x) + O (1) \approx n .

A string carries about $K (x)$ bits of information about itself and $O (1)$ bits about an independent string — the algorithmic mirror of $I (X; X) = H (X)$ and $I (X; Y) = 0$ .□

Example 15.45 (The discount from a computable relationship). Let $x$ be incompressible of length $n$ and let $y = x$ with every bit duplicated, so $∣ y ∣ = 2 n$ . Compute $K (y)$ and $I_{K} (x : y)$ .

Solution. Duplication and its inverse are fixed computable bijections between strings of length $n$ and the doubled strings of length $2 n$ , so Information is not increased by computation gives $K (y) = K (x) + O (1) \approx n + K (n)$ .

Then $K (x, y) = K (x) + K (y ∣ x^{*}) + O (1) = K (x) + O (1)$ , since $y$ is computed from $x$ outright. Hence

I_{K} (x : y) = K (x) + K (y) - K (x, y) = K (x) + O (1) \approx n .

Note the contrast with the literal bound: $y$ is a $2 n$ -bit string with $K (y) \approx n$ , so it is compressible by a factor of two — and Incompressible strings are statistically balanced is not violated, because $y$ is not incompressible; it is a string with an obvious regularity, which is exactly what the counting bound says almost no string has.□

Remark. Complexity is not monotone along prefixes: $K (x_{1 : n})$ can exceed $K (x_{1 : m})$ for $n < m$ . Take $x$ to be $Ω_{1 : n}$ followed by enough zeros: the longer string is easier to describe than its own prefix, because the zeros make the length cheap to state. Any intuition that "more data means more information" must be qualified accordingly.

Exercises for §15.8 →

15.9Martin-Löf Randomness for Infinite Sequences

For a finite string, "random" can only be a matter of degree: a fixed string of length $n$ has a fixed $K$ , and the choice of slack $c$ is a convention. For an infinite sequence the notion becomes sharp, and there is a genuine theorem to prove — that two definitions arrived at from completely different directions, one measure-theoretic and one descriptive, single out exactly the same sequences.

Martin-Löf's definition formalises "passes every statistical test that can actually be carried out".

Definition 15.46 (Martin-Löf test and randomness). A Martin-Löf test is a uniformly computably enumerable sequence of sets $V_{1} \supseteq V_{2} \supseteq \dots$ of finite strings, whose induced open sets $[V_{k}] \subseteq {0, 1}^{\infty}$ — the sequences having some element of $V_{k}$ as a prefix — satisfy $λ ([V_{k}]) \leq 2^{- k}$ , where $λ$ is the uniform (fair-coin) measure.

An infinite sequence $ω$ passes the test if $ω \in / ⋂_{k} [V_{k}]$ . It is Martin-Löf random if it passes every such test.

Each $[V_{k}]$ is the set of sequences rejected at significance level $2^{- k}$ ; enumerability is what makes the test effective, and the nesting lets the level be pushed arbitrarily low. A sequence that fails the test is rejected at every level — it is a genuine, effectively detectable non-randomness.

Theorem 15.47 (Universal test). There is a Martin-Löf test ${U_{k}}$ such that a sequence is Martin-Löf random if and only if it passes ${U_{k}}$ . Consequently the set of non-random sequences is a $λ$ -null set, and almost every sequence is Martin-Löf random.

Proof. Enumerate all candidate tests ${V_{k}^{(i)}}_{i}$ effectively — a candidate can be forced to satisfy the measure bound by truncating its enumeration whenever the accumulated measure would exceed $2^{- k}$ , which preserves enumerability and only shrinks genuine tests. Set

U_{k} = i \geq 1 ⋃ V_{k + i + 1}^{(i)} .

This is uniformly c.e. as a union of uniformly c.e. sets, and by subadditivity $λ ([U_{k}]) \leq \sum_{i \geq 1} 2^{- (k + i + 1)} = 2^{- (k + 1)} \leq 2^{- k}$ , so ${U_{k}}$ is a test. If $ω$ fails some test ${V_{k}^{(i)}}$ then $ω \in [V_{k}^{(i)}]$ for all $k$ , hence $ω \in [U_{k}]$ for all $k$ , so it fails ${U_{k}}$ .

For the last claim, $⋂_{k} [U_{k}]$ has measure at most $in f_{k} 2^{- k} = 0$ .∎

Now the descriptive side. The natural guess — call $ω$ random when its prefixes are incompressible — is false with plain complexity, and the failure is total: it excludes every sequence whatsoever.

Theorem 15.48 (Plain complexity oscillates (Martin-Löf)). For every infinite binary sequence $ω$ there are infinitely many $n$ with

C (ω_{1 : n} ∣ n) \leq n - lo g_{2} n + O (1) .

Hence no sequence satisfies " $C (ω_{1 : n} ∣ n) \geq n - c$ for all $n$ ", and plain complexity cannot define randomness for infinite sequences.

Proof. Fix $k$ and let $n = 2^{k} + ν$ , where $ν$ is the number whose $k$ -bit binary representation is $ω_{1} ω_{2} \dots ω_{k}$ . Then the binary representation of $n$ is $1 ω_{1} \dots ω_{k}$ , so from $n$ alone a machine recovers $k = ⌊ lo g_{2} n ⌋$ and the first $k$ bits of $ω$ .

Therefore, given $n$ , the string $ω_{1 : n}$ is determined by its last $n - k$ bits, and

C (ω_{1 : n} ∣ n) \leq (n - k) + O (1) = n - ⌊ lo g_{2} n ⌋ + O (1) .

Each $k$ produces a distinct $n \geq 2^{k}$ , so there are infinitely many such $n$ .∎

Figure 15.49. Why prefix complexity is the right tool. Against the diagonal

n

, plain complexity of the prefixes of any sequence dips to

n - lo g_{2} n

infinitely often (the sawtooth), so no sequence is plain-incompressible at every length; prefix complexity stays above

n - c

for a Martin-Löf random sequence, which is what makes the Levin–Schnorr characterisation possible.

Prefix complexity repairs exactly this, because its extra $lo g$ makes the length field free, and the repair is precise.

Theorem 15.50 (Levin–Schnorr theorem). An infinite sequence $ω$ is Martin-Löf random if and only if there is a constant $c$ with

K (ω_{1 : n}) \geq n - c for every n .

Proof. ( $\Leftarrow$ , contrapositive, in full.) Suppose $ω$ is not random, so it fails the universal test: $ω \in [U_{k}]$ for every $k$ . Fix $k$ . Since $λ ([U_{k}]) \leq 2^{- k}$ , we may enumerate $U_{k}$ and assign to its $j$ -th enumerated string $u$ a codeword of length $∣ u ∣ - k + O (lo g k)$ : the strings of $U_{k}$ have total measure $\sum 2^{- ∣ u ∣} \leq 2^{- k}$ , so by Kraft a prefix-free code with those lengths exists and can be built as the enumeration proceeds. A machine that reads $k$ self-delimitingly and then such a codeword prints $u$ , giving

K (u) \leq ∣ u ∣ - k + O (lo g k) for every u \in U_{k} .

Because $ω \in [U_{k}]$ , some prefix $ω_{1 : n}$ lies in $U_{k}$ , so $K (ω_{1 : n}) \leq n - k + O (lo g k)$ . As $k$ is arbitrary and $k$ outgrows $O (lo g k)$ , the deficiency $n - K (ω_{1 : n})$ is unbounded, so no constant $c$ works.

( $\Rightarrow$ , sketch.) Conversely, if the deficiency is unbounded, the sets $V_{k} = {u : K (u) \leq ∣ u ∣ - k}$ are uniformly c.e. because $K$ is upper semicomputable by K is upper semicomputable, and $λ ([V_{k}]) \leq \sum_{u \in V_{k}} 2^{- ∣ u ∣} \leq 2^{- k} \sum_{u} 2^{- K (u)} \leq 2^{- k}$ by Kraft. So ${V_{k}}$ is a Martin-Löf test, and $ω$ fails it. The only point suppressed is the nesting requirement, met by replacing $V_{k}$ with $⋂_{j \leq k}$ of the earlier levels.∎

Corollary 15.51 (Random sequences obey the law of large numbers). If $ω$ is Martin-Löf random then the frequency of ones in $ω_{1 : n}$ tends to $\frac{1}{2}$ .

Proof. The sets $V_{k} = {u : ∣ #_{1} (u) /∣ u ∣ - \frac{1}{2} ∣ > ε_{k}}$ , with $ε_{k}$ chosen by Chernoff's bound so that $λ ([V_{k}]) \leq 2^{- k}$ , form a Martin-Löf test; the bound is computable, so the sets are uniformly c.e. A sequence whose frequencies do not converge to $\frac{1}{2}$ lies in every $[V_{k}]$ and so fails the test.∎

Intuition. Randomness is the absence of any effectively detectable regularity, and the Levin–Schnorr theorem says that "effectively detectable regularity" and "short description" are the same thing. A regularity you can test for is a regularity you can compress with; a compression you can exhibit is a test the sequence fails.

Example 15.52 (Sorting three sequences). Classify as Martin-Löf random or not: (a) $0101010101 \dots$ ; (b) the binary expansion of $π$ ; (c) the binary expansion of $Ω$ ; (d) a random sequence with every odd-indexed bit replaced by $0$ .

Solution. (a) Not random: $K (ω_{1 : n}) = O (lo g n)$ , so the deficiency $n - O (lo g n)$ is unbounded. It also fails the frequency test only mildly — frequencies do converge to $\frac{1}{2}$ — which shows why Levin–Schnorr is stronger than any single statistical test.

(b) Not random, for the same reason: $K (π_{1 : n}) = O (lo g n)$ by A string that looks random and is not. Every computable sequence fails, since computability gives $K (ω_{1 : n}) \leq K (n) + O (1)$ .

(d) Not random: the sequence lies in the effectively closed set "odd positions are $0$ ", which has measure zero, and the corresponding test is trivially enumerable. Descriptively, $K (ω_{1 : n}) \leq n /2 + O (lo g n)$ .□

Pitfall. Martin-Löf randomness is not the only notion, and the differences are real. Computable randomness (no computable betting strategy wins) and Schnorr randomness (the tests must have computable measure) are strictly weaker; $2$ -randomness, defined relative to a halting oracle, is strictly stronger, and $Ω$ is Martin-Löf random but not $2$ -random. Claiming "random" without naming the class is meaningless at this level of precision.

Exercises for §15.9 →

15.10Induction, Learning, and the Reach of the Theory

The coding theorem said that algorithmic probability and description length are one quantity. Solomonoff's programme takes that quantity as a prior and derives a theory of prediction from it — arguably the only formal account of induction that requires no assumptions about the world beyond computability.

Prediction needs a measure over infinite sequences rather than over finite strings, so the machine model changes slightly: a monotone machine writes output as it reads input, never retracting, so that longer inputs extend rather than replace earlier output.

Definition 15.53 (Universal monotone semimeasure). For a universal monotone machine $U$ , let

M (x) = p : U (p) outputs a string beginning with x \sum 2^{- ∣ p ∣},

the sum being over minimal such $p$ . $M$ is a semimeasure on sequences: $M (ε) \leq 1$ and $M (x 0) + M (x 1) \leq M (x)$ . Solomonoff's predictor is the conditional

M (a ∣ x) = \frac{M ( x a )}{M ( x )} .

$M$ dominates every computable measure exactly as $m$ did, by the argument of Universality of the algorithmic prior: $M (x) \geq 2^{- K (μ)} μ (x)$ for every computable measure $μ$ . That single inequality is the whole engine of the following theorem.

Theorem 15.54 (Solomonoff's convergence theorem). Let $μ$ be a computable measure on infinite binary sequences, and let the data be generated by $μ$ . Then

t = 1 \sum \infty E_{μ} [(M (1 ∣ x_{< t}) - μ (1 ∣ x_{< t}))^{2}] \leq \frac{l n 2}{2} K (μ) + O (1) .

The sum being finite forces $M (1 ∣ x_{< t}) - μ (1 ∣ x_{< t}) \to 0$ with $μ$ -probability one: Solomonoff's predictor learns any computable environment, and the total error it ever makes is bounded by the complexity of that environment.

Proof. Let $D_{n} = E_{μ} [ln \frac{μ ( x _{1 : n} )}{M ( x _{1 : n} )}]$ , the relative entropy in nats between the true and predicted distributions on the first $n$ symbols. By domination, $M (x_{1 : n}) \geq 2^{- K (μ)} μ (x_{1 : n})$ pointwise, so $ln \frac{μ}{M} \leq K (μ) ln 2$ everywhere and hence

D_{n} \leq K (μ) ln 2 for every n .

The chain rule for relative entropy expands $D_{n}$ as the sum over $t \leq n$ of the expected one-step relative entropies $E_{μ} [d_{t}]$ , where $d_{t}$ is the relative entropy between the true and predicted conditional distributions at step $t$ . Pinsker's inequality in the binary case gives $d_{t} \geq 2 (M (1 ∣ x_{< t}) - μ (1 ∣ x_{< t}))^{2}$ in nats. Summing over $t$ and using the uniform bound on $D_{n}$ ,

2 t = 1 \sum n E_{μ} [(M - μ)^{2}] \leq D_{n} \leq K (μ) ln 2,

which is the claim after dividing by $2$ and letting $n \to \infty$ . (The $O (1)$ absorbs the constant in the domination inequality.)∎

Remark. The claim must be stated honestly, because it is routinely overstated.

Convergence is $μ$ -almost sure and in mean square; it says nothing about the sequences of $μ$ -measure zero, and every specific sequence you might name could be one of them.
There is no computable bound on when the error becomes small. The bound $\frac{l n 2}{2} K (μ)$ limits the total error but not its distribution over time, and $K (μ)$ is itself uncomputable.
$M$ is not computable — it is only lower semicomputable — so Solomonoff induction is not an algorithm. It is an upper bound on what any prediction method could achieve, and a standard against which computable methods are measured.
The environment must be computable. If the world contains a source of genuine algorithmic randomness that no program simulates, the theorem simply does not apply.

The practical descendants of the theory replace the uncomputable $K$ by a computable stand-in, and the substitution is honest as long as one remembers that all such stand-ins are upper bounds.

Definition 15.55 (Minimum description length). The minimum description length principle selects the model $M$ minimising

L (M) + L (D ∣ M),

the number of bits to describe the model plus the number of bits to describe the data given the model, where $L$ is a fixed computable code — a practical substitute for $K$ . The minimum message length principle is the Bayesian variant, with $L (M) = - lo g_{2} P (M)$ for an explicit prior.

The two terms are the fit-versus-complexity trade-off priced in the same units, which is why MDL requires no separate regularisation parameter.

Example 15.56 (MDL on a curve fit). Model $M_{1}$ costs $30$ bits to describe and leaves residuals costing $100$ bits; model $M_{2}$ costs $200$ bits and leaves residuals costing $10$ bits. Which does MDL choose, and by what margin does the loser fail?

Solution. $L_{1} = 30 + 100 = 130$ bits and $L_{2} = 200 + 10 = 210$ bits, so MDL selects $M_{1}$ by $80$ bits.

Read the margin as an accounting statement: $M_{2}$ bought a $90$ -bit reduction in residual cost for a price of $170$ extra bits of model. It spent more than it saved, which is exactly what overfitting is — the extra parameters were not paid for by the data. Had $M_{2}$ 's residuals come in at $10$ bits for a model description of only $100$ bits, the totals would have been $130$ against $110$ and MDL would have switched, correctly, to the more complex model.□

Definition 15.57 (Time-bounded complexity and Levin search). Levin's $K t$ complexity is

K t (x) = p min {∣ p ∣ + lo g_{2} t (p) : U (p) = x in t (p) steps} .

Levin search runs every program $p$ for $2^{∣ p ∣ - i}$ steps at stage $i$ , dovetailing; it finds a program producing $x$ within a factor $2^{K t (x)}$ of optimal time.

Theorem 15.58 (Optimality of Levin search (stated)). For any problem whose solutions can be verified in time $v$ , Levin search finds a solution in time $O (2^{∣ p ∣} (t_{p} + v))$ , where $p$ is any program that solves the problem and $t_{p}$ is its running time. The constant $2^{∣ p ∣}$ is multiplicative and independent of the input size.

Remark. $K t$ is computable — it is the time-bounded quantity, and boundedness is exactly what restores computability. The price is that $K t$ is no longer machine-independent in the tidy way $K$ is: the $lo g_{2} t$ term shifts by a constant factor under simulation, not a constant summand. It is a working compromise, not a canonical measure.

Definition 15.59 (Normalised information distance). The information distance between $x$ and $y$ is $E (x, y) = max {K (x ∣ y), K (y ∣ x)}$ , and the normalised information distance is

NID (x, y) = \frac{max { K ( x ∣ y ) , K ( y ∣ x )}}{max { K ( x ) , K ( y )}} \in [0, 1] .

Replacing $K$ by the output length of a real compressor $Z$ gives the computable normalised compression distance

NCD (x, y) = \frac{Z ( x y ) - min { Z ( x ) , Z ( y )}}{max { Z ( x ) , Z ( y )}} .

Example 15.60 (NCD on two files). A compressor reports $Z (x) = 4000$ bytes, $Z (y) = 5000$ bytes and $Z (x y) = 5600$ bytes. Compute the NCD and interpret it.

Solution.

NCD (x, y) = \frac{5 600 - 4 000}{5 000} = \frac{1 600}{5 000} = 0.32.

Interpretation: compressing $y$ after $x$ costs only $1600$ bytes instead of the $5000$ it costs alone, so about $68%$ of $y$ 's compressible content is already predictable from $x$ . Values near $0$ mean near-identity, values near $1$ mean no shared structure. Had the files been unrelated, $Z (x y)$ would have been near $9000$ and the NCD near $1$ .

The sanity check that matters in practice: $NCD (x, x)$ should come out near $0$ , and it does only if $Z$ has a window long enough to see the repeat. A compressor with a $900$ -byte window would report $Z (xx) \approx 8000$ and an NCD near $1$ for identical files — an artefact of $Z$ , not of the mathematics.□

Pitfall. NCD is not an approximation of NID in any controlled sense. $K$ is uncomputable and $Z$ is an upper bound with no bound on the error, so NCD inherits none of NID's metric guarantees; the triangle inequality can fail outright. NCD works in practice because real compressors detect the redundancies real data has, which is an empirical claim about data, not a theorem.

Exercises for §15.10 →

Common Mistakes

Confusing $K (x)$ with Shannon entropy $H (X)$ . $K$ is defined for an individual object, $H$ for a distribution. They meet only on average, through Expected complexity equals entropy: $H (P) \leq E [K (X)] \leq H (P) + K (P) + O (1)$ .
Treating the invariance constant as small. It is uniform in $x$ , but for any single string it can swallow the entire statement. Only asymptotic claims are machine-independent.
Reading "looks random" as "incompressible". The digits of $π$ , and the output of any pseudorandom generator with a short seed, pass every practical statistical test and have complexity $O (lo g n)$ .
Reading "incompressible" as "meaningless". $Ω$ is Martin-Löf random and encodes the halting problem. Algorithmic randomness is a statement about description length, not about significance.
Believing $K$ can be computed, or even lower-bounded, by a compressor. Every compressor gives an upper bound. By No computable unbounded lower bound, no computable function is an unbounded lower bound for $K$ , so no experiment certifies incompressibility.
Confusing plain $C$ with prefix $K$ . They differ by $O (lo g n)$ , which is invisible in most statements and decisive in two: the exact chain rule, which holds only for $K$ , and randomness for infinite sequences, where Plain complexity oscillates rules $C$ out entirely.
Forgetting that the length is not free. $K (x) = n + K (n) + O (1)$ for typical $x$ of length $n$ , not $n + O (1)$ ; the $K (n)$ term is the difference between $K (x)$ and $K (x ∣ n)$ .
Stating the chain rule with $x$ instead of $x^{*}$ . $K (x, y) = K (x) + K (y ∣ x) + O (1)$ is false; the error term is $O (lo g)$ , and closing it requires conditioning on a shortest program, not on the string.
Overstating Solomonoff induction. It converges $μ$ -almost surely for computable $μ$ , with no computable rate, and the predictor itself is uncomputable. It is a benchmark, not a method.
Using MDL or NCD as though they were $K$ . They are computable substitutes with uncontrolled error, and their guarantees are empirical.

About the practice questions. They check that you can carry out this chapter's computations correctly, and each one is graded on a single answer. They are not proof exercises: working through them confirms the mechanics, not that you could prove the results yourself. For that, re-read the statements above and try to reconstruct their proofs with the page closed.

Practice this chapter