Skip to content

Intuiting the Halting Problem

Posted on:October 12, 2020

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 "", line 13, in <module>
  File "", line 4, in eternity
    return eternity()
  File "", line 4, in eternity
    return eternity()
  File "", 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 x1:

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.



  1. I’ve called it x in lieu of a proper name because the name is unimportant here.