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 x1:

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.

Wikipedia entry on the halt­ing prob­lem.

Foot­notes


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