Oracles and the Halting Problem

[Tiberius]

Because it might be completely acceptable that there exists an algorithm A such that it cannot be known whether A halts. In fact, the 'solution' to the halting problem--i.e., that there is no solution--exhibits just such an algorithm.

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.