(November 27, 2012 at 2:29 pm)apophenia Wrote:
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.
“The truth of our faith becomes a matter of ridicule among the infidels if any Catholic, not gifted with the necessary scientific learning, presents as dogma what scientific scrutiny shows to be false.”
