Oracles and the Halting Problem

[CliveStaples]

Not sure I understand you, or maybe you don't understand the halting problem.

You stated there was a proof that "there is no algorithm that solves the halting problem for every algorithm." As such, there cannot be an algorithm which solves the halting problem for every algorithm...that's what a proof means.

So, it cannot be completely acceptable that such an algorithm exists...the proof says categorically that it doesn't. The solution to the halting problem is not an algorithm...it's the statement that such an algorithm cannot possibly exist.

So, we have the following:

1) There exists no algorithm that can solve the halting problem.
2) If God is omniscient, he can solve the halting problem (that is, for any algorithm, he can tell you whether or not it halts).
3) If 2 is true, then an algorithm exists that solves the halting problem (your example of basically just asking God).
4) But it has already been proven that there is no algorithm that solves the halting problem. So God cannot be omniscient.

It's a simple case of either no algorithm exists, or God is omniscient. Since it can be proven that no algorithm exists, God cannot be omniscient.

Right, so it's (2) that's up for grabs. As I stated in the OP:

I'm wondering how this result intersects with the notion of an entity/object that possesses something like omniscience. So in theory, God knows everything that can be known (for example, He can't know a fact x such that knowing x entails a contradiction). Essentially He acts as a flawlessly accurate oracle.

And then later in the post:

So, it seems, either there exists an algorithm A such that it can't be known whether A halts, or God can't possibly possess omniscience.

If A exists, then it can't be known whether A halts, therefore God can't know whether A halts. Thus A wouldn't have an entry on God's list. This would contradict (2).