Plain Kolmogorov complexity · Computability Theory

The string $0000\cdots0$ of length one million can be described in a few words, while a typical string obtained by tossing a coin one million times seems to admit no description shorter than itself. Kolmogorov complexity makes this distinction precise: the complexity of a string is the length of its shortest description, where descriptions are inputs of an algorithm that reconstructs the string. The definition depends on the algorithm, but only up to an additive constant, provided that the algorithm is optimal. This lesson sets up the definition, proves that most strings are incompressible, and shows that the complexity function is not computable.

1.1 Conventions

We work with binary strings $\bstr$ . Natural numbers are identified with strings through the length-lexicographic enumeration $\varepsilon, 0, 1, 00, 01, 10, 11, 000, \dots$ : the number $n$ is the $n$ -th string in this list, counting from $0$ . The string associated with $n$ has length $\lfloor \log(n + 1) \rfloor$ , where $\log$ denotes the logarithm in base $2$ . The number of strings of length less than $n$ is $2^n - 1$ .

We fix a computable bijection $\langle \cdot, \cdot \rangle : \bstr \times \bstr \to \bstr$ for coding pairs. All partial computable functions between countable sets of finite objects are understood through these codings.

1.2 Description machines

Definition 1.1.#

A machine is a partial computable function $M : \bstr \to \bstr$ . If $M(\tau) = \sigma$ , the string $\tau$ is an $M$ -description of $\sigma$ . The complexity of $\sigma$ relative to $M$ is

C_M(\sigma) = \min \{ |\tau| : M(\tau) = \sigma \},

with $C_M(\sigma) = \infty$ if $\sigma$ has no $M$ -description.

For instance, the identity machine gives $C_M(\sigma) = |\sigma|$ , and the machine $\tau \mapsto 0^{n}$ , where $n$ is the number coded by $\tau$ , describes $0^n$ with about $\log n$ bits. A machine that compresses some strings well may compress others badly; the following notion selects the machines that are optimal up to a constant.

We write $f \leq^+ g$ if there is a constant $c$ such that $f(x) \leq g(x) + c$ for every $x$ , and $f =^+ g$ if $f \leq^+ g$ and $g \leq^+ f$ .

Definition 1.2.#

A machine $U$ is optimal, or universal, if for every machine $M$ there is a constant $c_M$ with $C_U(\sigma) \leq C_M(\sigma) + c_M$ for every string $\sigma$ , that is, $C_U \leq^+ C_M$ .

Theorem 1.3 (Invariance theorem; Solomonoff, Kolmogorov).#

There is an optimal machine. If $U$ and $V$ are optimal, then $C_U =^+ C_V$ .

Proof of Theorem 1.3.

Let $(M_e)$ be an enumeration of the machines, with $M_e(\tau) = \Phi_e(\tau)$ through the identification of strings with numbers. Define $U(0^e 1 \tau) = M_e(\tau)$ , and let $U$ be undefined on the strings of the form $0^e$ . Every string other than $0^e$ decomposes uniquely as $0^e 1 \tau$ , so $U$ is well defined, and it is partial computable by the universality of the enumeration. If $\tau$ is an $M_e$ -description of $\sigma$ , then $0^e 1 \tau$ is a $U$ -description of $\sigma$ of length $|\tau| + e + 1$ . So $C_U \leq C_{M_e} + e + 1$ .

If $U$ and $V$ are optimal, then $C_U \leq^+ C_V$ by optimality of $U$ applied to the machine $V$ , and symmetrically.

We fix an optimal machine $U$ once and for all, and write $C(\sigma) = C_U(\sigma)$ , the (plain) Kolmogorov complexity of $\sigma$ . By the invariance theorem, the statements of the form $f \leq^+ g$ involving $C$ do not depend on this choice. For a number $n$ , $C(n)$ is the complexity of the string associated with $n$ .

Proposition 1.4.#

$C(\sigma) \leq^+ |\sigma|$ .
For every partial computable function $f : \bstr \to \bstr$ , $C(f(\sigma)) \leq^+ C(\sigma)$ for every $\sigma$ in the domain of $f$ .
$C(n) \leq^+ \log n$ for $n \geq 1$ , and $C(|\sigma|) \leq^+ C(\sigma)$ .

Proof of Proposition 1.4.

Apply the optimality of $U$ to the identity machine.
The machine $M(\tau) = f(U(\tau))$ satisfies $C_M(f(\sigma)) \leq C(\sigma)$ : a shortest $U$ -description of $\sigma$ is an $M$ -description of $f(\sigma)$ . Conclude by optimality.
The first inequality is 1, since the string associated with $n$ has length $\lfloor \log(n+1) \rfloor \leq \log n + 1$ . The second is 2 with $f(\sigma) = |\sigma|$ .

The second item says that an algorithm cannot create information: the complexity of the output of a computation is bounded by the complexity of its input, up to a constant depending only on the algorithm.

1.3 Incompressible strings

Definition 1.5.#

A string $\sigma$ is $c$ -incompressible if $C(\sigma) \geq |\sigma| - c$ .

Proposition 1.6.#

For every $n$ and $c$ , fewer than $2^{n-c}$ strings $\sigma$ satisfy $C(\sigma) < n - c$ . In particular, for every $n$ there is a string of length $n$ with $C(\sigma) \geq n$ , and at least $2^n - 2^{n-c}$ strings of length $n$ are $c$ -incompressible.

Proof of Proposition 1.6.

A string $\sigma$ with $C(\sigma) < n - c$ has a description of length less than $n - c$ , and distinct strings have distinct descriptions, since $U$ is a function. There are $2^{n-c} - 1$ strings of length less than $n - c$ .

So at least half of the strings of each length are $1$ -incompressible, and the proportion of strings of length $n$ that can be compressed by more than $c$ bits, that is, with $C(\sigma) < n - c$ , is less than $2^{-c}$ . Incompressibility is the first formal approximation of randomness for finite strings: a string with a regularity that an algorithm can exploit is compressible.

Example 1.7.#

$C(0^n) =^+ C(n) \leq^+ \log n$ for $n \geq 1$ : item 2 of Proposition 1.4, applied to the computable function $n \mapsto 0^n$ , gives $C(0^n) \leq^+ C(n)$ , and item 3 gives $C(n) = C(|0^n|) \leq^+ C(0^n)$ .
If $\sigma$ has length $2n$ and the bits of $\sigma$ at odd positions are all $0$ , then $C(\sigma) \leq^+ n$ : a description is the string of the bits at even positions.
Let $\sigma$ be a string of length $n$ containing exactly $k$ ones. It is determined by $n$ , $k$ and its rank among the $\binom{n}{k}$ strings of length $n$ with $k$ ones. When $k \leq n/4$ , the number $\log \binom{n}{k}$ is at most $n h(1/4) < 0.82\, n$ , where $h(p) = -p \log p - (1 - p) \log (1 - p)$ is the binary entropy function, and $\sigma$ is compressible by a linear number of bits for large $n$ . For the bound, let $p = k/n$ with $0 < k \leq n/4$ : the term of index $k$ in the binomial expansion of $(p + (1 - p))^n = 1$ gives $\binom{n}{k} p^k (1 - p)^{n - k} \leq 1$ , that is, $\log \binom{n}{k} \leq n h(p)$ , and $h(p) \leq h(1/4)$ since $h$ is increasing on $[0, 1/2]$ . The triple is coded with a logarithmic overhead by the technique of Proposition 1.8 below.

1.4 Pairs

The complexity of a pair is not bounded by the sum of the complexities. A description of $\sigma$ followed by a description of $\tau$ does not tell where the first one ends. The length of the first description has to be coded as well.

Proposition 1.8.#

$C(\langle \sigma, \tau \rangle) \leq^+ C(\sigma) + C(\tau) + 2 \log C(\sigma)$ , where $\log 0$ is read as $0$ .

Proof of Proposition 1.8.

For a string $\rho = \rho_0 \cdots \rho_{k-1}$ , let $\bar\rho = \rho_0 \rho_0 \rho_1 \rho_1 \cdots \rho_{k-1} \rho_{k-1}$ . A string of the form $\bar\rho\, 01\, \alpha$ determines $\rho$ and $\alpha$ : read pairs of bits until the first pair $01$ . Let $M$ be the machine that, on an input of the form $\bar\rho\, 01\, \alpha$ , interprets $\rho$ as a number $\ell$ , splits $\alpha = \alpha_0 \alpha_1$ with $|\alpha_0| = \ell$ , and outputs $\langle U(\alpha_0), U(\alpha_1) \rangle$ . If $\alpha_0$ and $\alpha_1$ are shortest descriptions of $\sigma$ and $\tau$ , and $\rho$ is the string of the number $|\alpha_0| = C(\sigma)$ , the input has length $2|\rho| + 2 + C(\sigma) + C(\tau)$ , and $|\rho| \leq \log C(\sigma) + 1$ . Conclude by optimality of $U$ .

The logarithmic term cannot be replaced by a constant. Fix $n \geq 1$ . There are $(n + 1) 2^n$ pairs $(\sigma, \tau)$ with $|\sigma| + |\tau| = n$ , and their codes $\langle \sigma, \tau \rangle$ are distinct. By the argument of Proposition 1.6, fewer than $2^{n + \lfloor \log n \rfloor} \leq n 2^n$ strings have complexity less than $n + \lfloor \log n \rfloor$ , so one of these pairs satisfies $C(\langle \sigma, \tau \rangle) \geq n + \lfloor \log n \rfloor$ . With $d$ such that $C(\rho) \leq |\rho| + d$ for every $\rho$ , this pair also satisfies $C(\sigma) + C(\tau) \leq n + 2d$ , so the difference is at least $\lfloor \log n \rfloor - 2d$ , which is unbounded. This defect motivates the prefix-free complexity of a later lesson.

1.5 Non-computability

Theorem 1.9.#

The function $C$ is not computable. More precisely, if $g : \bstr \to \nat$ is a partial computable function such that $g(\sigma) \leq C(\sigma)$ for every $\sigma$ in its domain, then $g$ is bounded.
The function $C$ is approximable from above: there is a computable function $(s, \sigma) \mapsto C_s(\sigma)$ , non-increasing in $s$ , with $\lim_s C_s(\sigma) = C(\sigma)$ .

Proof of Theorem 1.9.

Suppose that $g$ is unbounded on its domain. Let $f(n)$ be the first string $\sigma$ found, in an enumeration of the domain of $g$ , with $g(\sigma) > n$ . Then $f$ is total computable, and $C(f(n)) \geq g(f(n)) > n$ . By Proposition 1.4, $C(f(n)) \leq^+ C(n) \leq^+ \log n$ . So $n < \log n + c$ for some constant $c$ and every $n \geq 1$ , which fails for large $n$ . If $C$ were computable, it would be such a function $g$ , and it is unbounded by Proposition 1.6.
Let $d$ be a constant with $C(\sigma) \leq |\sigma| + d$ for every $\sigma$ . Let $C_s(\sigma)$ be the least length of a string $\tau$ with $|\tau| \leq |\sigma| + d$ and $U(\tau)[s]\converge = \sigma$ , or $|\sigma| + d$ if there is none. It is computable, non-increasing in $s$ , and equal to $C(\sigma)$ from the stage at which a shortest description converges.

The proof formalizes the Berry paradox, “the least number that cannot be defined in fewer than twenty words”: the first string of complexity larger than $n$ has a description of length about $\log n$ . Statement 1 says more than non-computability: no algorithm certifies that strings have large complexity, except for finitely many values. This is a form of Gödel’s incompleteness theorem, due to Chaitin. Let $T$ be a theory with a c.e. set of axioms that proves only true statements of the form " $C(\sigma) > n$ ". Searching through the proofs of $T$ enumerates the set $S$ of pairs $(\sigma, n)$ such that $T$ proves " $C(\sigma) > n$ ". If $S$ contained pairs with arbitrarily large second coordinate, the function $f(m)$ , the first $\sigma$ found such that $(\sigma, n) \in S$ for some $n > m$ , would be total computable with $C(f(m)) > m$ , and the argument of 1 would give a contradiction. So there is a number $n_0$ such that $T$ proves no statement " $C(\sigma) > n$ " with $n \geq n_0$ , although all but finitely many strings satisfy $C(\sigma) > n_0$ .

The approximation from above makes $C$ computable in $\emptyset'$ : $C(\sigma)$ is the value of $C_s(\sigma)$ at the first stage $s$ such that no description shorter than $C_s(\sigma)$ ever converges, and whether a given $s$ has this property is the negation of a c.e. condition, which $\emptyset'$ decides. Conversely, $C$ computes $\emptyset'$ : this is the second exercise below, after a first exercise that proves the same for the domain of $U$ .

1.6 Exercises

Exercise 1.10 ★.

Let $X$ be the set of strings $\sigma$ such that $U(\sigma)$ converges. Show that $\emptyset' \leq_T X$ .

Solution

Let $M$ be the machine with $M(0^e) = 0^s$ , where $s$ is the least stage with $\Phi_e(e)[s]\converge$ , and $M$ undefined elsewhere. Let $d$ be such that $C \leq C_M + d$ . If $\Phi_e(e)$ converges at stage $s$ , then $C(0^s) \leq e + d$ . With oracle $X$ , list the strings $\tau$ of length at most $e + d$ such that $U(\tau)$ converges, compute their outputs, and let $t$ be the largest number such that $0^t$ is one of them ( $t = 0$ if there is none). Then $\Phi_e(e)$ converges if and only if $\Phi_e(e)[t]\converge$ .

Exercise 1.11 ★★.

Show that $\emptyset' \leq_T C$ , where $C$ is used as an oracle through its graph.

Hint

Adapt the previous solution: when $\Phi_e(e)$ converges at stage $s$ , describe with about $e$ bits a string of length $2e$ that has no short description converging by stage $s$ .

Solution

Let $M$ be the machine defined on the strings $0^e$ as follows: search for the least $s$ with $\Phi_e(e)[s]\converge$ , and output the first string $\sigma$ of length $2e$ , in the lexicographic order, such that $U(\tau)[s] \converge = \sigma$ for no $\tau$ of length less than $2e$ . Such a string exists, since fewer than $2^{2e}$ strings are outputs of strings of length less than $2e$ . Let $d$ be such that $C \leq C_M + d$ , and let $e > d$ .

With oracle $C$ , compute the finite set $S$ of strings $\sigma$ of length $2e$ with $C(\sigma) < 2e$ , and then a stage $t$ such that every $\sigma \in S$ satisfies $U(\tau)[t]\converge = \sigma$ for some $\tau$ of length less than $2e$ ; the search for $t$ terminates, since every element of $S$ has such a description. If $\Phi_e(e)$ converges at stage $s$ , the string $\sigma = M(0^e)$ satisfies $C(\sigma) \leq e + d < 2e$ , so $\sigma \in S$ , and no description of $\sigma$ of length less than $2e$ converges by stage $s$ ; hence $s < t$ . So $\Phi_e(e)\converge$ if and only if $\Phi_e(e)[t]\converge$ . The finitely many $e \leq d$ are handled by a finite table.

Exercise 1.12 ★.

Fix $c$ . Show that the set $R_c = \{ \sigma : C(\sigma) \geq |\sigma| - c \}$ of $c$ -incompressible strings is immune: it is infinite and has no infinite c.e. subset.

Solution

$R_c$ contains a string of each length by Proposition 1.6, so it is infinite. If $W \subseteq R_c$ were an infinite c.e. set, the partial computable function $g(\sigma) = \max(|\sigma| - c, 0)$ with domain $W$ would satisfy $g \leq C$ on its domain, and it would be unbounded, since $W$ contains strings of arbitrary length. This contradicts Theorem 1.9.

1.7 Notes and references

Solomonoff (1960–1964), Kolmogorov (1965) and Chaitin (1966) introduced the complexity of strings independently, with different motivations: inductive inference, the definition of information and randomness, and the length of programs. Chaitin’s form of the incompleteness theorem dates from 1974. Kummer (1996) proved that the set of compressible strings $\{ \sigma : C(\sigma) < |\sigma| \}$ is truth-table complete, a stronger form of the second exercise. Li and Vitányi’s book is the standard reference on Kolmogorov complexity.

A. N. Kolmogorov, Three approaches to the quantitative definition of information, Problems of Information Transmission 1 (1965), 1–7.
R. J. Solomonoff, A formal theory of inductive inference I, Information and Control 7 (1964), 1–22.
G. J. Chaitin, Information-theoretic limitations of formal systems, Journal of the ACM 21 (1974), 403–424.
M. Kummer, On the complexity of random strings, STACS 96, Lecture Notes in Computer Science 1046, Springer, 1996, 25–36.
M. Li and P. Vitányi, An Introduction to Kolmogorov Complexity and Its Applications, 4th edition, Springer, 2019.