Berry, Kolmogorov and the Halting Problem: A Paradoxical Journey

How the Berry paradox, Kolmogorov complexity, Solomonoff induction, Occam’s razor, the Halting problem and Goldbach’s conjecture relate to each other

The expression fifteen defines the number 15, and so does the expression ten plus five. So here we have two expressions that define the same number. In fact, there are infinitely many such expressions: there are infinitely many positive integers greater than 15, so we can already generate an infinite list of such expressions starting with sixteen minus one, seventeen minus two, etc. You may even know that 0.999… (with infinite 9’s) is equal to 1. Not convinced? Say x = 0.999… Then 10x = 9.999…, and 9x = 10x - x = 9.999… - 0.999… = 9. If 9x = 9, x = 1.

So far, so good. But we can consider more interesting expressions. What about the largest positive integer definable in under 60 letters? There are exactly 26 letters in the alphabet we’re using, so the amount of phrases of under 60 letters is finite — for example, the amount of phrases of exactly 59 letters is 26 to the power of 59, or 26⁵⁹. That means we can define only a finite number of positive integers in under 60 letters, one of which must be the largest. So which is it? How do we define it? We already did: the largest positive integer definable in under 60 letters itself defines this positive integer in under 60 letters. Isn’t that fun?

It sure is. But now consider the smallest positive integer not definable in under 60 letters. It seems like this expression should define a positive integer too, right? But that’s a paradox: if the smallest positive integer not definable in under 60 letters defines a positive integer, then — by definition — that positive integer is not definable in under 60 letters. But the smallest positive integer not definable in under 60 letters defines this positive integer, and has less than 60 letters. So the expression can’t define a positive integer!

This is known as the Berry paradox, and as it turns out, a variant of this result can be used to prove why Kolmogorov complexity is uncomputable. So let’s first discuss Kolmogorov complexity!

Let’s start with a question: which string (sequence of letters or characters) is more complex: abcabcabcabcabcabcabc or qazwsxedcrfvtgbyhnujm? Well, what do we mean by complex? Both strings are equally long (21 letters), for example. That’s true, but imagine we want a computer to put these strings on the screen. Since abcabcabcabcabcabcabc is just abc repeated 7 times, we can write something like the following:

print(7 * "abc")

That’s efficient! We can’t do something like that for qazwsxedcrfvtgbyhnujm, as it doesn’t contain any repetitions. We can still write a program, but it’s longer (even though the string’s length is the same as abcabcabcabcabcabcabc’s):

print("qazwsxedcrfvtgbyhnujm")

So the program to produce qazwsxedcrfvtgbyhnujm is longer than the program for abcabcabcabcabcabcabc, and that means that qazwsxedcrfvtgbyhnujm’s Kolmogorov complexity is larger than abcabcabcabcabcabcabc’s.

So the Kolmogorov complexity of a thing is just the length of the shortest computer program (in some specified programming language) to produce that thing. It’s a useful concept, for example for Solomonoff induction: in short, this is a method to, in theory, find the theory — of all possible theories — that best explains the available data. If two or more theories explain the data equally well, the “simplest” theory wins — where simple can be measured in terms of Kolmogorov complexity. This way, Solomonoff induction formalizes Occam’s razor.

To give an example in the context of Solomonoff induction: if Theory 1 explains how apples fall with a formula and how the Moon moves around the Earth with another formula, while Theory 2 explains both phenomena with a single formula (that’s no more complex than any of the two formulas of Theory 1) then Theory 2 wins.

Okay, so we’ve defined Kolmogorov complexity. Let’s write a computer program that calculates Kolmogorov complexity for any given string s, shall we?

function kolmogorovComplexity(string s):
  for i = 1 to infinity:
    for each string p where length(p) == i:
      if isProgram(p) and output(p) == s:
        print(i)

So we have an iterator i that goes from 1 to infinity — that is, first i = 1, then i = 2, i = 3, etc. For each i (1, 2, 3, …), our function considers every string of that length. So for i = 1 the function considers a, b, c, etc., for i = 2 it considers aa, ab, ac, …, ba, bb, bc, etc. For each of these strings, our function asks: is this a valid computer program? And if so, does it produce s as output? Since our function goes over all possible strings of increasing length, when it does finally find a program that produces s, this must be the shortest program possible.

Cool, right? Sure, but our kolmogorovComplexity() function can’t possibly work on every string, for the same reason the smallest positive integer not definable in under 60 letters can’t define a positive integer. We can easily write a new, short function that uses kolmogorovComplexity() to find a string of enormous Kolmogorov complexity (according to kolmogorovComplexity()). And that’s a paradox, because then we have a short computer program that outputs a string of high Kolmogorov complexity!

function complexString():
  for i = 1 to infinity:
    for each string s where length(s) == i:
      if kolmogorovComplexity(s) >= 999999999999999999999:
        print(s)

complexString() is much shorter than 999999999999999999999 characters (even with the code of kolmogorovComplexity()) included), and yet, it prints a string whose Kolmogorov complexity is supposedly larger than or equal to 999999999999999999999. That’s a clear paradox!

There is another problem with our function kolmogorovComplexity(): it’s considering all possible programs (given enough time), but some programs never stop running. For example, the following program never stops:

while(2 < 3):
  print("Hello world!")

This program will keep printing Hello world! as long as 2 < 3. But 2 is smaller than 3 by definition, so this program won’t stop running! And because kolmogorovComplexity() considers all programs (including the one above), that means kolmogorovComplexity() itself never stops running.

What’s worse, we can’t in general tell whether or not a given program will stop running. I mean, we can do this for some programs — like our 2 < 3 example above — but we can’t do this for every program. This is called the Halting problem, and it’s easily shown we can’t solve it.

To see why, assume for a moment we do have a function that decides, for every possible program you give it, whether or not this program halts (that is, eventually stops running). Call this function halts():

function halts(string p):
  if isProgram(p) and p halts: return 1
  else: return 0

The details here don’t matter — and if they did, I couldn’t give them, because this function can’t exist. The point is, for this proof, we consider a function halts() that returns 1 if the program we give it stops running and 0 otherwise. Note that a function stops running once it returns something: if it returns e.g. 1, it gives 1 as “answer” and then stops.

Now consider the function paradox():

function paradox(string p):
  if halts(p) == 0: return 1
  if halts(p) == 1:
    while(2 < 3):
      print("Hello world!")

paradox() takes a program (strictly speaking just a string) p as input. If p doesn’t halt, paradox returns 1 and stops running. If p does halt, paradox will keep printing Hello world! and thus keep running forever. Question: if we give paradox() itself as input to paradox() — in other words, we feed paradox() to itself — what will happen?

Well, fundamentally there seem to be two possibilities: either paradox() halts, or it doesn’t.

Say paradox() halts. Then halts() returns 1 when considering paradox(). But if halts() returns 1, paradox() keeps printing Hello world! and does not, in fact, halt. A paradox!

So paradox() doesn’t halt? But then halts() returns 0, and thus paradox() returns 1. Which means it does halt: it doesn’t keep running, as it returns 1. Again, we have a paradox!

So paradox() is paradoxing all over the floor, as we just proved it neither halts nor doesn’t halt. So it’s safe to say the Halting problem is undecidable: that is, we can’t possibly decide for every program whether or not it halts.

And that’s too bad! If the Halting problem were decidable, we could easily prove or disprove Goldbach’s conjecture.

What’s that? Let’s start with prime numbers: natural numbers greater than 1 that are only divisible by themselves and 1. The first 5 prime numbers are 2, 3, 5, 7 and 11. Goldbach’s conjecture states that every even natural number greater than 2 — so 4, 6, 8, 10, etc. — is equal to the sum of 2 prime numbers. 4 is equal to 2 + 2, 6 = 3 + 3, 8 can be written as 3 + 5, etc. The conjecture — conjectured in 1742 — remains unsolved to this day: it has been checked for many numbers, and is true for all those numbers, but it hasn’t been proven to be true for all even numbers greater than 2. (Note that this doesn’t make the checking “useless”: if any one of the checked numbers turned out to not be the sum of 2 primes, the conjecture would have been immediately disproven.)

Since all but one prime numbers are odd, the sum of 2 prime numbers is virtually always even

But if the Halting problem were decidable, we could easily prove or disprove Goldbach’s conjecture! Just write a program that checks for every even natural number 4, 6, 8, etc. whether or not it can be expressed as the sum of 2 prime numbers. So it starts with 4, determines that 4 can be expressed as 2 + 2, and moves on to 6. Then it moves on to 8, 10, etc. It stops running only if it comes across an even natural number greater than 2 that can’t be expressed as the sum of 2 prime numbers.

Now we can use the magic halts() function — which now works, because in our thought experiment, the Halting problem is decidable — to decide whether or not this program halts. If it does, then there must be an even natural number greater than 2 that can’t be expressed as the sum of two prime numbers and so the Goldbach conjecture must be false. If it doesn’t halt, the conjecture must be true!

Unfortunately, the Halting problem is undecidable, and the Goldbach conjecture remains unproven (and “un-disproven”) to this day. But at least we had some fun with these problems and paradoxes, didn’t we?

Thanks for reading!