Eric Holloway: Wrap up Experiment on Mutual Information

[swamidass (S. Joshua Swamidass)]

@EricMH

This is from Turing himself, the father of the field.

Can you cite where Turing proved halting oracles cannot exist? As far as I know, he only proved Turing machines cannot be halting oracles. I’d be extremely grateful and most likely reject ID if you can prove halting oracles are impossible.

Here it is:

@swamidass

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.

1. 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.
2. 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.