Is God a Halting Oracle?

[swamidass (S. Joshua Swamidass)]

Just remind people what a Halting Oracle is and how it is a logical impossibility:

@swamidass

So the Halting Oracle is a really good example to study further. It is proven that they do not exist in a proof by contradiction (Proof by contradiction - Wikipedia).

The Problem

Does a program exist that can examine the code of any other program to determine if it halts?

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.

Which gets to one divine loophole.

@swamidass

The contradiction arises because the halting oracle, also, is a program subject to inclusion in a program itself.

If God is more than a computational machine (which seems to be a very reasonable supposition) He cannot be called recursively in a way that creates the contradiction. So perhaps that one loophole that creates space for him to be halting oracle.