##### The problem

Previously we have solved a puzzle that claimed to be impossible but was, in fact, just a bit hard 😀 But in this post we will see a problem that is really impossible to solve, the halting problem:

Given a description of an arbitrary computer program, decide whether the program finishes running or continues to run forever.

For some programs it’s easy to see if they halt or not:

def program_1(): return 2 + 2 def program_2(): while True: pass def program_3(): from itertools import count for i in count(): if str(2**i)[0] == '7': break def program_4(): from itertools import count for i in count(): if str(2**i)[-1] == '7': break

For others it’s not so simple:

def program_5(): def z(m, n): if m == 0: return n + 1 elif n == 0: return z(m - 1, 1) else: return z(m - 1, z(m, n - 1)) z(4, 4)

And there are simple ones where it’s an open problem to know if they halt or not:

def program_6(): from itertools import count for i in count(1): p = 2 ** i r = int(''.join(reversed(str(p)))) for j in count(1): q = 5 ** j if q > r: break elif q == r: return

##### The proof

Let’s assume we have a procedure, represented by the function **does_halt()**, to determine if any given program will halt:

def does_halt(program): # # magic implementation #

We don’t care about the details of the **does_halt()** function. The only requirements are:

- Its implementation should be finite.
- It must accept any Python function that doesn’t take arguments as a
**program**. - It must give an answer in an easily bounded time. For example, we should be able to say “if the input program has 1000 bytes, the function should return a boolean value indicating if it halts in no more than NNN seconds”.

The clever point of the proof, though it’s not a new kind of cleverness, is to build a program that “halts only if it doesn’t”:

def paradox(): if does_halt(paradox): while True: pass

As the **paradox()** program is finite, including this small amount of code plus the code of **does_halt()**, **does_halt()** should return in a finite amount of time. If **does_halt()** returns **False**, indicating that **paradox()** does not halt, the program exits, finishing its execution in a finite time. On the other hand, if **does_halt()** returns **True**, indicating that **paradox()** does halt, it enters an infinite loop.

This proves that *some* of these propositions must be true:

**does_halt()**must not be finitely implementable.**does_halt()**must reject some valid programs.**does_halt()**execution time is unbounded.

[…] the previous post we have seen that the halting problem cannot be solved. But maybe the problem is just in our […]