Oracles and the Halting Problem

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