41J Blog

Godel’s incompleteness theorem is one of the most important and beautiful results in Computer Science. It tells us that even if we know exactly how a system is constructed there are statements about that system which are true, but we can never prove. They are in some sense unknowable truths.

However the usual presentation of Godel’s theorem is complicated and unwieldy. I could never really get my head around it, or find the time to dedicate to doing so. Even after gaining the jist of it, Godel’s description doesn’t leave me with the sense of awe that it perhaps should.

There is however another, less well known, description formulated in terms of Kolmogorov Complexity. It’s simple, beautiful, and certainly leaves me with a sense of awe. It somehow feels much more like a proof ‘should’. And runs as follows [1]:

1. Let x denote a finite binary string. We write “x is random” if the shortest description of x is at least as long as x. That is, we can’t write a computer program to generate x, that’s shorter than x. It’s incompressible.

2. We can see by a simple counting argument that there are random strings of every length. See note 2.

3. We have a language (formal system to use the precise terminology). In that language we can make statements like ‘x is random’. Now, suppose we can describe that language (F) in f bits of data. For example, this could be the number of bits required for an exhaustive description of the textbook ‘the language of F’. F can be a complicated language, but it must be consistent. No statement in F can be both true AND false, and only true statements can be proven to be true using F.

4. Now we’re going to show that there are statements in F which are true, but we can’t prove them ! Truths which exists that we can never know. We so this by contradiction. Given F we can start to exhaustively search for a proof that some string (which is a lot bigger than f) is random, and then print it when it’s found.

But wait! If you can prove it’s random it can’t be random! Why? Because the procedure to print it only required f + log n bits of data. Which is much smaller then n. Therefore we’ve proven something true, which is not true. Our language F is not consistent, and our axiom is violated.

So in short, you can have a system that’s consistent (things you can prove to be true, are really true) or a system which contains true statements but you can never know they are true…

I think it’s a stunning result! It tells us that whatever logical tool you use to look at the universal you will still fail to understand it completely. We are in some sense doomed to live in a state of unknowing, and must make peace with a certain degree of confusion.

——

Note 1: This form of the proof can be found on page 5 of “An Introduction to Kolmogorov Complexity and Its Applications”. Though I’m not sure that it originates here.

Note 2: That’s because there are 2^n strings of length n and sumof 2^(n-i) for i=1 to n-1 strings of length n-1 or smaller. As the number of strings of length n-1 is less than the number of strings of length n and our computer programs can be expressed as binary strings. It’s clear to see that there can’t be a 1 to 1 mapping between strings of length n and programs of length n-1 or less. There must be strings of length n with are random or ‘uncompressable’.