They exist but you cannot catch ’em

(“A few lines where incompressibility meets unprovability”)

The Kolmogorov Complexity $K(x)$ of a string $x$ relative to an Universal Turing machine $U$ is the length of the shortest program $p$ that “prints” $x$:

$$K(x) = min\{ |p| \mid U(p) = x \}$$

A string $x$ is incompressible if $K(x) \geq |x|$. Assuming a binary alphabet $\Sigma = \{0,1\}$, for each $n \geq 1$, there are $2^n$ strings of length $n$, but there are only $2^n-1$ programs shorter than $n$, so there is at least one incompressible string among them. And it follows immediately that there are infinite incompressible strings (they exist …).

Can we catch some of them? … No! Indeed if we are reasoning in a formal theory $T$ that is powerful enough to formalize Turing machines and the notion of compressibility – e.g. Peano Arithmetic – we have:

Theorem 1: There exists $n$ such that for all strings $x$ such that $|x| \geq n$ the statement “$K(x) \geq |x|$” (i.e. $x$ is incompressible) is unprovable in $T$.

Proof: Suppose that there are infinitely many strings $x$ such that there is a proof of “$K(x) \geq |x|$”. We can build a program $p$ that enumerates all valid proofs of $T$ and whenever it founds a proof of “$K(x_i) \geq |x_i|$” for some $x_i$, it compares $|x_i|$ with $|p|$ (by the recursion theorem we can build a program that knows its length), and if $|p| < |x_i|$ then $p$ halts and prints $x_i$.  So $T$ proves that $x_i$ is incompressible, but we can actually build a program shorter than $|x_i|$ which prints $x_i$, a contradiction.

Note that Theorem 1 is not provable in $T$ ! … we need $T + Con(T)$ to prove it, because no powerful enough theory can prove its own consistency or prove that some sentence is unprovable.

Using Kolmogorov complexity to solve the Halting problem

We assume that reader is familiar with the notions of undecidability, Turing reductions, Kolmogorov complexity, Halting problem, and related subjects.

The (easy) proof that the uncomputability of Kolmogorov complexity implies the undecidability of the Halting problem can be found in many lectures notes and books; usually the proof assumes that the Halting problem is decidable and derive the  computability of Kolmogorov complexity which is a contradiction. In other words given an oracle for the Halting problem, we can compute the Kolmogorov complexity of a string $x$.

But we can also derive the uncomputability of Kolmogorov complexity from the undecidability of the Halting problem; the proof is “less popular” but nevertheless can be found after a few searches on Google. For example the technical report: Gregory J. Chaitin, Asat Arslanov, Cristian Calude: Program-size Complexity Computes the Halting Problem. Bulletin of the EATCS 57 (1995) contains two different proofs, and the great book Li, Ming, Vitányi, Paul M.B.; An Introduction to Kolmogorov Complexity and Its Applications presents it as an exercise (with a hint on how to solve it that is credited to P. Gács by W. Gasarch in a personal communication Feb 13, 1992). Here we give an extended proof, with more details, that the Halting problem can be decided using an oracle that computes the Kolmogorov complexity of a string, i.e. that the Halting problem is Turing reducible to the Kolmogorov complexity. Continue reading