The Halting Problem¶

Suppose we have a program. We want to determine whether the program contains an infinite loop

Turing's result: it's impossible to write an algorithm to accomplish this.

Here are some examples: an input would for example be a string like:

'''def f():
  while True:
    pass'''

(Obviously, that's an infinite loop.)

Possibly, it would be a string like this:

'''def g():
   n = 3
   while True:
     if n % 2 == 0 and is_prime(n):
       return
      n += 1'''

This is also an infinite loop, but we need some mathematical insight in order to figure it out: it's an infinite loop because there are no prime even numbers greater than 2.

Finally, here's a function that we saw already. People took hundreds of years to finally prove Fermat's Last Theorem, which says that fermat(3) would produce an infinite loop for

 '''def fermat(p):
        n = 1
        while True:
            for i in range(1, n):
                for j in range(1, n):
                    for k in range(1, n):
                        if i**p + j**p == k**p:
                            return i, j, k
            n += 1'''

Here is a hypothetical function that we'd like to write:

Turing's result is that you cannot write a function like that. It just doesn't exist.

Assume that we can write a function halt() as defined above. We'll get to a contradiction, which will mean that our assumption that it's possible to write halt() is false!

Here is how we can arrive at a contradiction. Let's define the function confused().

Assume the function was called using confused(confused). Then: f = confused inside the call to confused().

Now, suppose confused(confused) halts. Then halt(confused, confused) is True, which means that we'll enter the infinite loop! So it can't be that confused(confused) halts.

Now, suppose that confused(confused) does not halt. Then Then halt(confused, confused) is False, which means we don't enter the infinite loop! So it can't be that confused(confused) doesn't halt.

So confused(confused) doesn't halt, and also doesn't not halt. That's impossible.

The problem is that we assumed that halt(f, x) can be written in the first place -- it can't, since assuming that it can leads to a contradiction.

Godel's Incompleteness Theorem¶

Here's a simplified statement of the Theorem: "There are true statements about arithmetic that cannot be proven."

We'll show that if any true statement can be proven, we can write halt(f, x). But we can't, which means that there are statements that cannot be proven.

Claim: any proof can be checked (TRUE, trust me).

Here's how we can write halt(f, x):

Generate all strings s over the latin alphabet
  For every s, check if it's a correct proof that f(x) halts
               check if it's a correct proof that f(x) doesn't halt

Eventually, if we keep checking all the strings, we'll get to a proof that f(x) halts, or we'll reach a proof that f(x) doesn't halt. That way we can answer the question of whether f(x) halts or not!

BUT HALT IS IMPOSSIBLE TO WRITE, so something went wrong. What went wrong is the assumption that any true statement has a proof.

I can't give you an example of such a statement (because I can't prove that it's true, by design!) But this is a proof that those statements are out there.