I’ve always struggled to understand an intuition of the proof behind the Halting problem. Reading the Little Schemer this weekend fixed that for me. I’ll try to share what I understand of it as simply as possible, and I’ll do it in Python, since re-writing it in Python helped strengthen my own understanding of it.

Let’s say we have a function eternity:

def eternity():
    return eternity()

Clearly, this function will never stop once started. Running this function yields a RecursionError:

> eternity()
 
Traceback (most recent call last):
  File "halting.py", line 13, in <module>
    eternity()
  File "halting.py", line 4, in eternity
    return eternity()
  File "halting.py", line 4, in eternity
    return eternity()
  File "halting.py", line 4, in eternity
    return eternity()
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

Then, we define a hypothetical function does_it_ever_stop, which takes another function as an argument, and returns True if the function can terminate or False if the function doesn’t:

def does_it_ever_stop(f):
    ... do something

As an example what this function should be able to do, running does_it_ever_stop(eternity) should return False.

Lastly, we define another hypothetical function x¹:

def x():
    return does_it_ever_stop(x) and eternity()

Now, we’ve glossed over the implementation for does_it_ever_stop, but let’s just say here that does_it_ever_stop(x) returns True. In that case, we will go on to evaluate the second term in the and operator, which is eternity(). Since eternity() runs forever, x itself will run forever and contradict the initial assumption that does_it_ever_stop(x) == True.

If we instead assume does_it_ever_stop(x) returns False, then it will short-circuit and return without evaluating eternity(). This contradicts the initial assumption that does_it_ever_stop(x) == False.

Therefore, defining such a function does_it_ever_stop is impossible.

Wikipedia entry on the halting problem.

#Footnotes