The Proof
This is adapted from here: https://en.wikipedia.org/wiki/Halting_problem#Proof_concept
Suppose that there exists a total computable function halts(f) that returns true if the subroutine f halts (when run with no inputs) and returns false otherwise.
Now consider this program.
def g():
if halts(g):
loop_forever()
Now ask, does halts(g) return true or false? Either way we get a contradiction.
- If halts(g) returns True, then g() will execute loop_forever(), and will therefore not halt, resulting in a contradiction, because halts(g) should have returned False.
- If halts(g) returns False, then g() will halt, resulting in a contradiction, because halts(g) should have returned True.
Therefore we know that a Halting Oracle is not logically possible.