Fix some programming language. For any string x, we define K(x) (the Kolmogorov complexity of x) to be the bit length of the shortest program that outputs x and halts, when fed the empty string as input. I’m going to prove some neat results about Kolmogorov complexity.
K(x) ≤ |x|
Our first result: for every x, K(x) ≤ |x|. This is because in the worst case, you can always just literally have your program write out the string. (Technically, there might be a constant overhead, like writing “print()” in Python, but we will subtract out this constant overhead from our definition of K(x) so that the above equality holds.)
Most binary strings have high Kolmogorov complexity
In particular, at most 1/2k of strings have K(x) < |x| – k
- Half of all binary strings have K(x) < |x| – 1
- A quarter have K(x) < |x| – 2
- One eighth have K(x) < |x| – 3
Here’s the proof. Define A to be the set of all binary strings of length n with K(x) ≤ n – k. Define B to be the set of all binary strings of length n. So |A|/|B| is the proportion of all length-n strings with K(x) < n – k.
Now, |B| = 2n. And there’s an injection from A to programs of binary length < n – k. So |A| ≤ the number programs of binary length < n – k. But this is at most 2n-k.
So |A|/|B| < 2n-k/2n = 1/2k.
This means that if we’re looking at strings of length 100, the proportion of them that have K(x) < 90 is at most 1/210 = 1/1024 ≈ 0.1%. Said another way, more than 99.9% of length 100 strings have Kolmogorov complexity 90 or up (i.e. can only be compressed by at most 10 bits).
K(x) is uncomputable
There is no program that takes in a pair (x, k) and halts, outputting yes if K(x) = k and no if K(x) ≠ k. Let’s prove it.
Suppose that P is such a program. We use P to create a program Q that takes as input a number k and generates the first binary string y such that K(y) > k. Here’s how Q works: Enumerate all programs in lexicographic order (0, 1, 00, 01, 10, 11, 000, and so on). For each program x, apply P to check if K(x) = k. Output the first one for which the answer is yes.
Let’s give the name y to the output of Q on input k. Now, K(y) = k, because P says so. So the shortest program that outputs y has bit-length k. But notice that Q is also a program that outputs y! So the bit-length of Q has be at least k. But what is the bit-length of Q? Well, Q contains P as a subroutine, and writing Q requires that you also write out k. So |Q| = |P| + |k| + c (c is some constant overhead). But |k| is just the number of bits required to write out the number k, which is at most log2(k).
So, K(y) = k ≤ |Q| ≤ log2(k) + |P| + c. And this identity must hold no matter WHAT k we choose. So it must be that for all k, k ≤ log2(k) + some constant. But this can’t be true! After all, k – log2(k) goes to infinity as k goes to infinity! Contradiction.
The uncomputability of Kolmogorov complexity allows us to easily prove some of the most important and fun results in theoretical computer science. First of all:
The halting problem is undecidable
In other words, there is no program that takes as input a program P and outputs whether P will halt when run on the empty string.
Proof: Suppose that H is such a program. We can design a program using H to compute Kolmogorov complexity. Here’s how we do it: On input (x, k), enumerate all programs in lexicographic order. On each program Q, apply H to check if Q halts on empty string as input. If so, move on to the next program. If not, run Q to see if it outputs x.
This finds the shortest program y that outputs x. Now just look at the bit-length of y! If y has length k, then output yes, and otherwise output no. So if we can solve the halting problem, then we can also compute Kolmogorov complexity. But we just showed that you can’t do this! Contradiction.
The Busy Beaver numbers are uncomputable
Define BB(N) to be the maximum number of steps run by a program with length N before halting (only looking at those length-N programs that do halt, of course).
We prove that there is no program that takes as input a number N and outputs BB(N). Suppose Y is such a program. We can use Y to design a program H that solves the halting problem. Here’s how:
H takes as input a program P, uses Y to evaluate BB(|P|), and then runs P for BB(|P|) steps. If P hasn’t halted by the end of this, then P will never halt. So H outputs yes if P halts after BB(|P|) steps, and otherwise outputs no. This solves the halting problem, but we just showed that you can’t do this! Contradiction.
The Busy Beaver numbers grow faster than every computable function.
This is actually a very similar proof to the last one. Suppose f(n) is a computable function that grows faster than BB(n). Use f(n) to construct g(n) = f(n) + c, such that g(n) > BB(n) for all n. g(n) is computable, so let Y be a program that computes g(n).
We can design a program H that solves the halting problem using Y. H takes as input a program P, then uses Y to evaluate g(|P|), then runs P for g(|P|) steps. If P hasn’t halted by the end of this, then P will never halt. So H outputs yes if P halts after g(|P|) steps, and otherwise outputs no.
This solves the halting problem, but we just proved you can’t do this! Contradiction.
Gödel’s first incompleteness theorem
Yes that’s right, we’re going to prove this using Kolmogorov complexity! The theorem says that there is no recursively enumerable proof system which is sound and complete for the natural numbers.
Suppose F is such a proof system. We can use F to design a program P that takes as input x and k and computes whether K(x) = k. First, translate K(x) = k into a question about natural numbers. Then run through every string s in our proof system, checking at each step if s is a valid proof in F of K(x) = k, or of K(x) ≠ k. If either one of these is true, terminate and return which one. Since F is sound and complete, this algorithm eventually terminates and tells us which is true.
So if F existed, then we could compute Kolmogorov complexity. But we can’t compute Kolmogorov complexity! Contradiction. So there can not be any recursively enumerable proof system which is sound and complete for the natural numbers.
There’s an upper bound on what Kolmogorov complexities we can prove a string to have.
The proof of this closely resembles G. G. Berry’s paradox of ‘the first natural number which cannot be named in less than a billion words’ [P. R.: But this sentence names the very number in 14 words!]… The version of Berry’s paradox that will do the trick is ‘that object having the shortest proof that its algorithmic information content is greater than a billion bits.
Chaitin (1982)
For any sound proof system F, there’s a number L such that F cannot prove that the Kolmogorov complexity of any specific string of bits is more than L.
Suppose not. Then there’s some proof system F that is sound for N, such that for any L, F can prove that K(x) = L for some x.
First we design a program P that takes as input L and outputs a string x such that K(x) = L. P searches through proofs in F until it finds a proof that K(x) = L for some x, and then outputs x. F can prove this for any L by assumption.
Okay, so for each L, P(L) gives an x such that K(x) = L. So the shortest program that outputs x must be at least length L. But P(L) is a program that outputs x. So it must be that |P(L)| < L. But |P(L)| = |P| + |L| + c ≤ |P| + log2(L) + c (for the same reasons as before). So it must be that for all L, L < |P| + log2(L) + c. But as L goes to ∞, (L – log2(L)) goes to ∞. So we can find an L such that L > |P| + log2(L) + c. Contradiction!
We just showed that there’s some L for which we cannot prove that the Kolmogorov complexity of any string is L. But notice that if we take this L and add one, L+1 will still be larger than |P| + log2(L+1) + c. And same for L+2, L+3, and so on forever. So really we’ve shown that there’s an L for which we can’t prove that the Kolmogorov complexity of any string is L or greater.
John Baez calls this the “complexity barrier” and argues here that the L is probably not actually that big. He guesses that L is a few thousand digits long at most!