Oracles and the Halting Problem

[CliveStaples]

So being a Christian who is interested in mathematics and the more theoretical aspects of science, I've come across the proof that there is no algorithm that solves the halting problem for every algorithm.

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.

So, given some arbitrary algorithm A, God looks at A and knows whether it halts. God then tabulates this in a countably infinite mental list. God therefore has a list of all algorithms, and a corresponding accurate list of whether or not the given algorithm halts. You can then construct an algorithm that takes as input a given algorithm, looks it up in God's list, and returns whether that algorithm halts. This violates the previously established result that no such algorithm can exist.

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.


Can anyone more knowledgeable than myself give me either some pushback or maybe point me in the direction of a source that discusses oracles vis-a-vis the halting problem?

[Tiberius]

Or...why don't you just accept that this proof demonstrates that God can't possibly possess omniscience?

[CliveStaples]

Or...why don't you just accept that this proof demonstrates that God can't possibly possess omniscience?

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.

Another issue is that I'm not familiar enough with decidability, Turing machines, or computer science in general to be able to say what the specific caveats are for the halting problem 'solution'. Which is why I solicited more knowledgeable opinions.

[Anomalocaris]

Proof in computational science: god as descibed can not exist

Christian, nominally interested in "theoretical" aspects of "science", says on an atheist forum: therefore it is better to ignore the proof.

---

Generalizing:

Proof: A therefore not B

Christian: invalid, because god can do anything!

[CliveStaples]

Proof in computational science: god as descibed can not exist

Christian, nominally interested in "theoretical" aspects of "science", says on an atheist forum: therefore it is better to ignore the proof.

---

...? I never said that anyone should ignore any proof.

It's more like this:

P -> (Q or R)

Someone says, "This means that P implies R!" I say, "Well, no, because we know Q is true. We don't have enough to determine whether R is true from P -> (Q or R)."

How does that amount to "We should ignore a proof"?

Generalizing:

Proof: A therefore not B

Christian: invalid, because god can do anything!

???

Where did I say anything like "That proof is invalid because God can do anything"??????

[Angrboda]

Well, ignoring the mathematics, elegant as they are, God did not arrive at his list by way of an algorithm in the meaning of Turing's thesis, so it doesn't violate the Turing theorem unless you are suggesting that God's omniscience is algorithmically obtained. I may not have an algorithm which could solve the traveling salesman problem for a million nodes within a year's time; however if I obtained an exhaustive list of such answers, my being able to index that list does not change the facts of the inability to computationally derive the result in said time.

A related concept in computer science is the Turing oracle, being a machine (or device) that is able to derive a result using nondeterministic methods. Since a traditionally conceived Turing machine operates completely deterministically, the things that can be accomplished with the use of a Turing oracle differ radically from those that a standard Turing machine can accomplish. (I don't know offhand, but I would suspect that the problems solvable by a standard Turing machine in finite time are a proper subset of those solvable with a Turing oracle.)

(ETA: A quick check of Wikipedia indicates that my understanding of a Turing oracle is somewhat incorrect. If interested, I suggest you research the matter independently.)

[CliveStaples]

Well, ignoring the mathematics, elegant as they are, God did not arrive at his list by way of an algorithm in the meaning of Turing's thesis, so it doesn't violate the Turing theorem unless you are suggesting that God's omniscience is algorithmically obtained. I may not have an algorithm which could solve the traveling salesman problem for a million nodes within a year's time; however if I obtained an exhaustive list of such answers, my being able to index that list does not change the facts of the inability to computationally derive the result in said time.

A related concept in computer science is the Turing oracle, being a machine (or device) that is able to derive a result using nondeterministic methods. Since a traditionally conceived Turing machine operates completely deterministically, the things that can be accomplished with the use of a Turing oracle differ radically from those that a standard Turing machine can accomplish. (I don't know offhand, but I would suspect that the problems solvable by a standard Turing machine in finite time are a proper subset of those solvable with a Turing oracle.)

(ETA: A quick check of Wikipedia indicates that my understanding of a Turing oracle is somewhat incorrect. If interested, I suggest you research the matter independently.)

Interesting points, although I don't think it's relevant whether God generates the list algorithmically. The point is that He can search it algorithmically.

[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.

[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).

[Tiberius]

No...2 is not up for grabs. 2 is a complete contradiction of 1, and 1 has been proven.

Your question postulates that either the halting problem can be solved, or God is not omniscient. Well, we know the halting problem cannot be solved. So therefore God cannot be omniscient. Unless I'm getting confused here?