Intuiting the Halting Problem

October 12, 2020

I’ve always strug­gled to under­stand an intu­ition of the proof behind the Halt­ing prob­lem. Read­ing the Little Schemer this week­end fixed that for me. I’ll try to share what I under­stand of it as simply as pos­si­ble, and I’ll do it in Python, since re-writ­ing it in Python helped strength­en my own under­stand­ing of it.

Let’s say we have a func­tion `eternity`:

``````def eternity():
return eternity()``````

Clear­ly, this func­tion will never stop once start­ed. Run­ning this func­tion 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 hypo­thet­i­cal func­tion `does_it_ever_stop`, which takes anoth­er func­tion as an argu­ment, and returns `True` if the func­tion can ter­mi­nate or `False` if the func­tion does­n’t:

``````def does_it_ever_stop(f):
... do something``````

As an exam­ple what this func­tion should be able to do, run­ning `does_it_ever_stop(eternity)` should return `False`.

Lastly, we define anoth­er hypo­thet­i­cal func­tion `x`1:

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

Now, we’ve glossed over the imple­men­ta­tion 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 eval­u­ate the second term in the `and` oper­a­tor, which is `eternity()`. Since `eternity()` runs for­ev­er, `x` itself will run for­ev­er and con­tra­dict the ini­tial assump­tion that `does_it_ever_stop(x) == True`.

If we instead assume `does_it_ever_stop(x)` returns `False`, then it will short-cir­cuit and return with­out eval­u­at­ing `eternity()`. This con­tra­dicts the ini­tial assump­tion that `does_it_ever_stop(x) == False`.

There­fore, defin­ing such a func­tion `does_it_ever_stop` is impos­si­ble.

Foot­notes

1. I’ve called it `x` in lieu of a proper name because the name is unim­por­tant here.