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) == '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
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.