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 "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`1:

``````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.

#Footnotes

#Footnotes

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