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
def eternity(): return eternity()
Clearly, this function will never stop once started. Running this function yields a
> 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
Lastly, we define another hypothetical function
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
True. In that case, we will go on to evaluate the second term in the
and operator, which is
eternity() runs forever,
x itself will run forever and contradict the initial assumption that
does_it_ever_stop(x) == True.
If we instead assume
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.
I’ve called it
xin lieu of a proper name because the name is unimportant here. ↩