Oracles and the Halting Problem

[Angrboda]

In order for the list to be searched, it must first exist. The list may be generated algorithmically or non-algorithmically. The halting problem says the list cannot be generated algorithmically. Therefore, for the list to be generated, it has to be generated non-algorithmically, which removes it from the purview of the halting problem.

Moreover, it raises the specter of the question of correctness. In computer science, we're taught how to mathematically analyze an algorithm or program for correctness. Correctness being the property that the given algorithm or program will yield the correct result, tautologically. The proof of the correctness of an algorithm, assuming it exists, rests on those mathematical and logical assumptions that underpin the proof. Especially, the belief that such methods are robustly deterministic. If not, then correctness seems to lose all meaning. Let's suppose God provides you with this list. How do you determine its correctness? Verify one entry? A random sampling? The majority? All of them? Suppose you check all of them and God comes back and tells you he gave you the wrong list, that the list he gave you was for some other question, which just happened to be exactly the same list as the one he gave you for the halting problem. Is that list, the wrong list, a 'correct' solution to the halting problem?

[jonb]

I don't understand. Why do you Clive pursue this question? What ever the answer is it will make no difference to you. In christian theology God operates outside the fabric of this existence and yet can alter and interact with it, as such any laws do not matter.

So what is your motivation? I don't think what is going on here is confined to you personally, as there is a consistently here in christian philosophy of asking questions where there can be argument, but no conclusion, the How many angels can stand on the point of a needle debates.
It seems to me these pointless debates, have a purpose, which is to distract, as long as your mind can be absorbed in rolling over the arguments in these pointless propositions, christians will not have to examine the obvious central question, and so can claim to believe in something which at heart they know is false.

So is this just an attempt to keep your faith?

[CliveStaples]

I don't understand. Why do you Clive pursue this question? What ever the answer is it will make no difference to you. In christian theology God operates outside the fabric of this existence and yet can alter and interact with it, as such any laws do not matter.

That's a theological question--Can God do things that entail contradiction? What are the limits of God's ability to interact and alter the world?--that is off-topic in this thread. This thread isn't about that question. Please try to stay on topic =D

So what is your motivation? I don't think what is going on here is confined to you personally, as there is a consistently here in christian philosophy of asking questions where there can be argument, but no conclusion, the How many angels can stand on the point of a needle debates.

This isn't asking "how many angels can dance on the point of a needle". This is asking "Does the kind of omniscience God is claimed to have entail contradiction in light of results in theoretical computer science?"

It is an attempt to understand better both the nature of theoretical computer science (specifically, the halting problem) and the nature of omniscience (i.e., whether it entails contradiction, what kinds of limits it has, etc.).

It seems to me these pointless debates, have a purpose, which is to distract, as long as your mind can be absorbed in rolling over the arguments in these pointless propositions, christians will not have to examine the obvious central question, and so can claim to believe in something which at heart they know is false.

So is this just an attempt to keep your faith?

If you think it's pointless, feel free not to contribute to the thread. Wildly speculating that I secretly think God doesn't exist and am merely using this thread as a psychological device to maintain my self-deception...well, that's rather non-responsive to my OP. Try to stay on-topic please! =D

---

In order for the list to be searched, it must first exist. The list may be generated algorithmically or non-algorithmically. The halting problem says the list cannot be generated algorithmically. Therefore, for the list to be generated, it has to be generated non-algorithmically, which removes it from the purview of the halting problem.

It does? Where?

Moreover, it raises the specter of the question of correctness. In computer science, we're taught how to mathematically analyze an algorithm or program for correctness. Correctness being the property that the given algorithm or program will yield the correct result, tautologically. The proof of the correctness of an algorithm, assuming it exists, rests on those mathematical and logical assumptions that underpin the proof. Especially, the belief that such methods are robustly deterministic. If not, then correctness seems to lose all meaning. Let's suppose God provides you with this list. How do you determine its correctness? Verify one entry? A random sampling? The majority? All of them? Suppose you check all of them and God comes back and tells you he gave you the wrong list, that the list he gave you was for some other question, which just happened to be exactly the same list as the one he gave you for the halting problem. Is that list, the wrong list, a 'correct' solution to the halting problem?

I'm at a bit of a loss here. Asking how you verify that the list is correct is a different kind of question than asking whether a list with the given property would solve the halting problem. Do you see the difference?

Imagine that I said, "Every number divisible by 4 is divisible by 2." I might proceed by saying something like, "Suppose n is divisible by 4." I might then make a series of deductions using the axioms of arithmetic and conclude, "Therefore, n is divisible by 2."

It would not amount to a serious challenge or a disproof if you were to ask, "But how could you verify that the n you selected was, indeed, divisible by 4?" Verification of divisibility by 4 is a different question than whether divisibility by 4 entails divisibility by 2.

[jonb]

Please try to stay on topic =D

So it is off topic to question the validity of the topic?

Why do you seek such this boundary, if my viewpoint has not got validity?
If my argument had no validity it could be shown, rather than just dismissed.

[Tiberius]

In order for the list to be searched, it must first exist. The list may be generated algorithmically or non-algorithmically. The halting problem says the list cannot be generated algorithmically. Therefore, for the list to be generated, it has to be generated non-algorithmically, which removes it from the purview of the halting problem.

It does? Where?

The list you mentioned was one that God had which had every possible algorithm on it, and whether or not it halted. Such a list is cannot be generated (nor can it even exist) since it would violate the entire proof that Alan Turing set about in 1936:

"Alan Turing proved in 1936 that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist."

If such a list could exist, then as you said before, there would be an algorithm for determining whether any given program halted (simply search the list until you find the algorithm). However, this determination algorithm would clearly meet the criteria for being the general algorithm that Alan Turing proved cannot exist. Therefore, the list cannot exist either (since all lists are searchable).