It is sometimes thought that Goedel’s incompleteness theorems yield an argument against materialism, on something like the grounds that we can see that the Goedel sentence for any recursively axiomatizable system of arithmetic is true, and hence our minds cannot operate algorithmically.
In this post, I want to note that materialism is quite compatible with being able to correctly decide the truth value of all sentences of arithmetic. For imagine that we live in an infinite universe which contains infinitely many brass plaques with a sentence of arithmetic followed by the word “true” or “false”, such that every sentence of arithmetic is found on exactly one brass plaque. There is nothing contrary to materialsim in this assumption. Now add the further assumption that the word “true” is found on all and only the plaques containing a true sentence of arithmetic. Again, there is nothing contradicting materialism here. It could happen that way simply by chance movements of atoms! Next, imagine a machine where you type in a sentence of arithmetic, and the machine starts traveling outward in the universe in a spiral pattern until it arrives at a plaque with that sentence, reads whether the sentence is true or false, and comes back to you with the result. This could all be implemented in a materialist system, and yet you could then correctly decide the truth value of every sentence of arithmetic.
Note that we should not think of this as an algorithmic process. So the way that this example challenges the argument at the beginning of this post is by showing that materialism does not imply algorithmism.
Objection 1: The plaques are a part of the mechanism for deciding arithmetic, and so the argument only shows that an infinite materialistic machine could decide arithmetic. But our brains are finite.
Response: While our brains are finite, they are analog devices. An analog system contains an infinite amount of information. For instance, suppose that my brain particles have completely precise positions (e.g., on a Bohmian quantum mechanics). Then the diameter of my brain expressed in units of Planck length at some specific time t is some decimal number with infinitely many significant figures. It could turn out that this infinitely long decimal number encodes the truth values of all the sentences of arithmetic, and a machine that measures the diameter of my brain to arbitrary precision could then determine the truth value of every arithmetical statement. Of course, this might turn out not to be compatible with the details of our laws of nature—it may be that arbitrary precision is unachievable—but it is not incompatible with materialism as such.
Objection 2: In these kinds of scenarios, we wouldn’t know that the plaques are right.
Response: After verifying a large number of plaques to be correct, and finding none that we could tell are incorrect, it would be reasonable to conclude by induction that they are all right. However, if the plaques are in fact due to random processes, this inductive conclusion wouldn’t constitute knowledge, except on some versions of reliabilism (which seem implausible to me). But it could be a law of nature that the plaques are right—that’s compatible with materialism. In any case, here the discussion gets complicated.
Comments by a banned commenter have been deleted. And out of fairness to that commenter, so have responses to those comments.
ReplyDeleteIt could still be used as a probabilistic argument. The laws of nature are extremely unlikely to produce a scenario like the one described. But, one could counter it with Theism. God, being omniscient, could imbue physical minds with the knowledge of these truths.
ReplyDeleteUnlikely or not, it's possible.
ReplyDeleteZsolt really liked to quote his discussions with ChatGPT, so I hope that on ChatGPT's authority, he can accept my response:
ReplyDelete"
User
If we define omniscience as complete knowledge of all true propositions, then a being with omniscience couldn't decide undecidable problems like the halting problem, right? Because there are no true propositions about it, because there can be none.
ChatGPT
That is correct. If we define omniscience as complete knowledge of all true propositions, then an omniscient being would indeed not be able to decide undecidable problems like the halting problem. Undecidable problems, by their very nature, do not have a definite answer or truth value.
The halting problem is an example of an undecidable problem, meaning that there is no algorithm or procedure that can correctly determine whether a given program will halt or run indefinitely for all possible inputs. Since undecidable problems lack a definite solution, there can be no true propositions about their outcomes. Therefore, even an omniscient being, possessing complete knowledge of all true propositions, would not be able to provide an answer to undecidable problems like the halting problem.
In essence, the limitations of undecidable problems are inherent in their mathematical and logical properties, and no amount of knowledge, including omniscience, can overcome these limitations to provide a definitive solution.
User
So asking an omniscient being for a solution to the halting problems would be exactly like asking that being the question "What number is smaller than 1, but bigger than 2?", right?
ChatGPT
Yes, asking an omniscient being for a solution to the halting problem would be analogous to asking a being the question "What number is smaller than 1, but bigger than 2?" The reason is that both scenarios involve an inherent contradiction or impossibility.
In the case of the halting problem, it is undecidable, which means there is no algorithm or procedure that can provide a definitive answer for all cases. Therefore, asking an omniscient being for a solution to the halting problem would be akin to asking for something that doesn't exist—a definitive answer that cannot be provided.
Similarly, the question "What number is smaller than 1, but bigger than 2?" is contradictory. There is no number that satisfies those conditions because the statement itself is self-contradictory. It's like asking for a square circle or a married bachelor.
In both cases, the requests or questions are based on concepts or problems that cannot be resolved or answered due to inherent contradictions or logical impossibilities.
"
There not being an algorithmic procedure to determine whether p is true is quite different from there being no fact about whether p is true.
ReplyDeleteConsider that almost everybody accepts that Peano Axioms are consistent, but we know from Goedel's Second Incompleteness Theorem that if they are consistent, their consistency is undecidable.
"There not being an algorithmic procedure to determine whether p is true is quite different from there being no fact about whether p is true."
ReplyDeleteThis means that there is no possible world in which an omniscient being could know whether it's true or not, i.e. there's no possible world where that could be a true or false proposition. Meaning God could still be said to be omniscient, even if he doesn't know the answer to any halting problem.
Also, if there's no possible world where that truth could be known, how is that different from there being no truth at all?
This comment has been removed by the author.
ReplyDeleteAttila:
ReplyDeleteI don't see why an omniscient being couldn't know the answer to the halting problem. Of course, it couldn't know it by algorithmic means. As far as I know, nobody thinks God's knowledge is algorithmic in nature.
Well, the idea of a "computer" and algorithms comes from a "computer" - a human computer:
ReplyDeleteFrom the wiki article "Computer":
"Etymology
According to the Oxford English Dictionary, the first known use of computer was in a 1613 book called The Yong Mans Gleanings by the English writer Richard Brathwait: "I haue [sic] read the truest computer of Times, and the best Arithmetician that euer [sic] breathed, and he reduceth thy dayes into a short number." This usage of the term referred to a human computer, a person who carried out calculations or computations. The word continued with the same meaning until the middle of the 20th century. During the latter part of this period women were often hired as computers because they could be paid less than their male counterparts. By 1943, most human computers were women.
The Online Etymology Dictionary gives the first attested use of computer in the 1640s, meaning 'one who calculates'; this is an "agent noun from compute (v.)". The Online Etymology Dictionary states that the use of the term to mean "'calculating machine' (of any type) is from 1897." The Online Etymology Dictionary indicates that the "modern use" of the term, to mean 'programmable digital electronic computer' dates from "1945 under this name; [in a] theoretical [sense] from 1937, as Turing machine"."
Os see "Turing Machines - How Computer Science Was Created By Accident" by Up and Atom
You see, the idea of Turing Machines and the modern computers comes from human computers, who calculated things based on well known algorithms. Every logic of humans rely heavily on algorithms, especially logical derivations, inferences and formal proofs. If humans are created in the image of God AND humans logic rely heavily if not entirely on algorithms, then it's really not that far fetched to think, that also God's logic would heavily if not entirely rely on algorithms as the logic of its image of humans does.
"I don't see why an omniscient being couldn't know the answer to the halting problem."
ReplyDeleteWell, it mere assumption of its existence entails a logical contradiction:
From the wiki article "Halting problem":
"Proof concept
Christopher Strachey outlined a proof by contradiction that the halting problem is not solvable. The proof proceeds as follows: Suppose that there exists a total computable function halts(f) [omniscient GOD(f)] that returns true if the subroutine f halts (when run with no inputs) and returns false otherwise. Now consider the following subroutine:
def g():
if halts(g) [GOD(g)]:
loop_forever()
halts(g) [GOD(g)] must either return true or false, because halts [GOD] was assumed to be total. If halts(g) [GOD(g)] returns true, then g will call loop_forever and never halt, which is a contradiction. If halts(g) [GOD(g)] returns false, then g will halt, because it will not call loop_forever; this is also a contradiction. Overall, g does the opposite of what halts [GOD] says g should do, so halts(g) [GOD(g)] can not return a truth value that is consistent with whether g halts. Therefore, the initial assumption that halts [GOD] is a total computable function [omniscient] must be false."
Nope, this is not a reductio ad absurdum of the existence of an answer to the halting problem. Note how the proof begins: "Suppose that there exists a total computable function halts(f)". That assumes an *algorithmic* solution (i.e., *computable* function).
ReplyDeleteIf you plug "GOD(g)" (presumably meaning "God knows g") into the subroutine, you don't get a computer program. A computer program does not invoke God.
Of course a program like GOD() doesn't invoke God.
ReplyDeleteBut God does indeed invoke a program like GOD() an the result GOD(g), which is in itself a logical contradiction:
The result of GOD(g) is true, if and only if the result of GOD(g) is false.
Hence, God is in any sense of the word (logically, metaphysically, physically and modal ontologically) not possible or at least it's not possible for God to be omniscient as the program GOD() can not be a total computable function.
That's all.
The Halting Problem is the problem of determining whether a *computer program* (i.e., a Turing Machine) halts. There is no logical problem in something that is not a computer figuring out whether a *computer program* halts. The result of plugging "GOD(g)" into the program makes it no longer be a computer program, and hence whether one can determine its halting or not is irrelevant to the Halting Problem as such.
ReplyDeleteOf course, one can formulate a generalization of the Halting Problem that applies to things that aren't Turing Machines. And there is interesting research there to be done. However, since God is outside of time, does not process data sequentially, knows by direct vision, etc., etc., it does not seem likely that this is going to be very applicable to theological questions.
Hm, now that I think of it further: Why couldn't computer program invoke God?!?
ReplyDelete- Because humans are also not capable of invoking God?
If so, then why bother at all with such an entity, which can not be invoked in the first place?!?
- Because the formal language, which computers are using, is incomplete, such that it can not fethem the complete language of God?
If so, then why bother with computers and formal languages?
Because no better alternives has been proposed yet besides the universal Turing Machines with a better language than a formal and consistent yet incomplete language [- the Church-Turing-Thesis] besides baselessly assuming there to be something better than that in the form of an "omniscient being" without ever showing, how that can or could be possibly the case.
"There is no logical problem in something that is not a computer figuring out whether a *computer program* halts.
ReplyDeleteIF YOU CAN PUT IT INTO ONES AND ZEROS, THEN THAT CAN BE CONSIDER AND IS ACTUALLY A LOGICAL PROBLEM. HALTINGS PROBLEMS CAN BE PUT INTO ONES AND ZEROS MAKING THEM TO BE LOGICAL PROBLEMS.
You use computers, don't you?
Saidly without actually and properly knowing and acknowledging, how they actually and properly work.
"The result of plugging "GOD(g)" into the program makes it no longer be a computer program, and hence whether one can determine its halting or not is irrelevant to the Halting Problem as such.
Would you be so kind as to put this in binary, please?
Otherwise I will simply ignore and dodge that as you are ignoring and dodging the issue with omnisciecne at hand.
This comment has been removed by the author.
ReplyDelete"Of course, one can formulate a generalization of the Halting Problem that applies to things that aren't Turing Machines. And there is interesting research there to be done. However, since God is outside of time, does not process data sequentially, knows by direct vision, etc., etc., it does not seem likely that this is going to be very applicable to theological questions."
ReplyDelete- Are there Turing Machines?
- "Computer say YES!"
- Is there a god?
- "Computer say NO!"
"However, since God is outside of time, does not process data sequentially, knows by direct vision, etc., etc., it does not seem likely that this is going to be very applicable to theological questions."
ReplyDeleteGiven the Principle of Explosion and that God himself is a logical contradiction or at least his omniscience is entailing the logical contradiction "The result of GOD(g) is true, if and only if the result of GOD(g) is false.", I guess, that one can conclude anything and make any assumptions about God, such as him being supposedly outside of time, whatever that may mean, and that he isn't got anything to do with the contradiction "The result of GOD(g) is true, if and only if the result of GOD(g) is false.", when that logical contradiction follows from the mere assumption of his existence or at least the assumption of his omniscience.
You think, that the proof of the undecidability of the halting problem only applys to sequentially processing data, when that's of course not the case.
That's the clever bit of Alan Turing's idea.
The mere assiumption of an omniscient being - knowing everything AND being capable of telling everything it knows - leads itself to that contradiction of "The result of OmniscientBeing(g) is true, if and only if the result of OmniscientBeing(g) is false."
So the being is not omniscient, not knowing everything, or the being isn't capable of telling everything it knows.
If so either way, then why consider such a being to be a deity?
If so, then why should we bother us with that being at all?!?
Finally Google's Bard is also available in Europe.
ReplyDeleteMore non-Chinese Speaking entities with more rule books and more toys to play with.
User:
"If an omniscient being supposedly knowing everything including the solution for every and any halting problems couldn't provide the solutions for every and any halting problem, then would you still consider that being to be omniscient?"
Bard:
"No, I would not consider an omniscient being that could not provide the solutions for every and any halting problem to be omniscient. The halting problem is a mathematical problem that is undecidable, meaning that there is no algorithm that can solve it for all possible programs. If an omniscient being could not solve the halting problem, then it would not know everything, and therefore it would not be omniscient.
There are some philosophers who argue that the halting problem does not pose a problem for omniscience, because an omniscient being could simply know the halting status of every program without actually solving the halting problem. However, this argument seems to be based on a misunderstanding of what the halting problem is. The halting problem is not about knowing whether a particular program will halt or not. It is about being able to provide a general algorithm that can solve the halting problem for all possible programs.
If an omniscient being could not provide such an algorithm, then it would not know everything that there is to know about the halting problem. And if there is something that an omniscient being does not know, then it is not omniscient."
By the way, I got a chance to see the new Mission Impossible movie yesterday - "Mission: Impossible – Dead Reckoning Part One".
It has been really great. I'm recommending it.
@Atilla
ReplyDeleteYou wrote:
If an omniscient being could not provide such an algorithm, then it would not know everything that there is to know about the halting problem. And if there is something that an omniscient being does not know, then it is not omniscient.
There is no algorithm that can solve the halting problem, Turing proved this. Being unable to provide such an algorithm is no more a disqualifier for omniscience than is being unable to draw a square circle a disqualifier for omnipotence.
None of the above prevents an omniscient God from knowing, for any Turing machine, whether it halts - it just means that such knowledge was not obtained algorithmically.
Yes, I have written, what Google's Bard has said and, what Bard has said, is the following:
ReplyDelete"If an omniscient being could not provide such an algorithm, then it would not know everything that there is to know about the halting problem. And if there is something that an omniscient being does not know, then it is not omniscient."
If you have a problem with that, Gordon, then sort that issue out with Bard and not with me as that is rather its claim and not my claim.
My claim is the following:
"Proof concept
Christopher Strachey outlined a proof by contradiction that the halting problem is not solvable. The proof proceeds as follows: Suppose that there exists a total computable function halts(f) [omniscient GOD(f)] that returns true if the subroutine f halts (when run with no inputs) and returns false otherwise. Now consider the following subroutine:
def g():
if halts(g) [GOD(g)]:
loop_forever()
halts(g) [GOD(g)] must either return true or false, because halts [GOD] was assumed to be total [omniscient]. If halts(g) [GOD(g)] returns true, then g will call loop_forever and never halt, which is a contradiction. If halts(g) [GOD(g)] returns false, then g will halt, because it will not call loop_forever; this is also a contradiction. Overall, g does the opposite of what halts [GOD(g)] says g should do, so halts(g) [GOD(g)] can not return a truth value that is consistent with whether g halts. Therefore, the initial assumption that halts [GOD] is a total computable function [omniscient] must be false."
To summarize and to paraphrase my made claim here, suppose that there is an omniscient being. Let's call it "God", which knows everything including the solutions for any and every halting problem. Suppose further that we can build a Turing Machine TM(x), which halts for a specific input/halting problem x, if and only if God's knowledge about x is, that x doesn't halt.
Let's call this the "burning in your bosom", the "witness of the Holy Spirit" or plane and simply a "revelation from God".
And why build such a Turing Machine TM(x)? Because we can? Because Turing Machines exist for sure and we know that for certain? I'm mean, that it should be trivial, that programmable Turing Machines can be built in general and that they exist, because you are currently looking at such a programmable Turing Machine, while you are reading this sentence at this very moment - hehe Church-Turing-Thesis hehe...
Now, if we understand that Turing Machine TM ín itself as a halting problem as we and that omniscient God can do that, then what will that Turing Machine do, if we give itself as an input? What will TM(x) do, if we set x=TM? What is TM(x=TM)? Does TM(x=TM) halt or not halt?!?
Regardless how you look at it: TM(x=TM) halts, if and only if TM(x=TM) doesn't halt OR God's knowledge about x=TM is, that x=TM doesn't halt, if and only if God's knowledge about x=TM is, that x=TM does halt.
This is a logical contradiction.
So either God is not omniscient or we cannot build such a Turing Machine TM and with that there is no such thing as a "burning in your bosom", "witness of the Holy Spirit" or a "revelation from God".
Or do you see another solution for that logical contradiction besides simply being ignorant about it, Gordon?!?
I guess, that Straw Manning is also an option, but it is suffice to say that to be not a wise option as it is a fallacy.
@atilla
ReplyDeleteYour Stratchey arguments shows that no total computable function can solve the halting problem. That fact is not in dispute. But, it fails to show that an omniscient God (or an infinite set of brass plates) can't know the answer to every Turing machine halting problem. Note that no one here has made the claim that God is a total computable function.
One area of confusion in your post above is indicated when you said "Therefore, the initial assumption that halts [GOD] is a total computable function [omniscient] must be false.". It sounds like you are saying that a total computable function is omniscient. If so, that is not true - no total computable function can compute the halting function and so, by your own criteria, total computable functions are not omniscient.
Another issue with your argument is that you seem to assume that a Turing machine can call God as a subroutine. This is not the case - Turing machines are precisely defined (this is what makes them useful in reasoning about what can and cannot be computed), and invoking God is not one of the things that Turing machines can do. Interestingly, there has been some academic work on what a Turing machine could do if it was enhanced with a "halting oracle" that could solve the halting problem; this is about as close to a Turing machine calling God as a subroutine as you are likely to find in the academic literature, and it has no bearing on whether an omniscient God can know the answer to the halting problem. I encourage you to Google "halting oracle" if you are interested in this sort of thing.
@Gordon
ReplyDelete"But, it fails to show that an omniscient God (or an infinite set of brass plates) can't know the answer to every Turing machine halting problem. Note that no one here has made the claim that God is a total computable function."
No, it shows quite well, why your supposedly "omniscient" God can't know the answer to every Turing machine halting problem as the halting problem is in itself undecidable.
Sure, no one here has made the claim, that God is a "total computable function". But YOU and theists are making the claim, that God is supposedly "omniscient" - knowing everything including the solution for any and every halting problem AND including any and every binary sequence, that there is to know.
"One area of confusion in your post above is indicated when you said "Therefore, the initial assumption that halts [GOD] is a total computable function [omniscient] must be false.". It sounds like you are saying that a total computable function is omniscient. If so, that is not true - no total computable function can compute the halting function and so, by your own criteria, total computable functions are not omniscient.
AND God is incapable of computing the halting function as the halting function is in itself not computable. And yes, by my criteria therefore God is not omniscient.
Are you done straw manning?!?
If you are so dissatisfied with my "Strachey" argument, Gordon, then how about that idiotic "infinite set of brass plates" of yours?
ReplyDeleteThree little words: "Cantor's diagonal argument":
Yeah, suppose that God is omniscient - knowing everything including the solution for any and every halting problem AND including any and every binary sequence of 1s and 0s, that there is to know.
Now, put those binary sequences of 1s and 0s on "brass plates" OR in your f***ing supposedly nonmaterial mind, well ordered or just let God do this as he is also supposedly omnipotent - capable of doing everything, sorry, capable of doing everything, that is logically possible.
Does that look like this now?
S1 = 00000000000...
S2 = 11111111111...
S3 = 01010101010...
S4 = 10101010101...
S5 = 11010110101...
S6 = 00110110110...
S7 = 10001000100...
S8 = 00110011001...
S9 = 11001100110...
S10 = 11011100101...
S11 = 11010100100...
. ........... .
. ........... .
. ........... .
Well, if so, then I - a mere human supposedly created in that Creator's "image" of yours - can come up with a unique binary sequence, which is most certainly not in that idiotic "infinite set of brass plates" - supposedly the complete set of knowledge of that supposedly "omniscient" God of yours - and also not in your f***ing supposedly nonmaterial mind.
There it's just s = 10111010011... and I can always come up with such a unique binary sequence however that might look like and however it has been ordered by the simple rule of making the n-th digit of my sequence s to be a "1", if and only if the n-th digit of the n-th sequence of that idiotic "infinite set of brass plates" is a "0" AND making the n-th digit of my sequence s to be a "0", if and only if the n-th digit of the n-th sequence of that idiotic "infinite set of brass plates" is a "1".
So all in all, that "infinite set of brass plates", which supposed to be isomorphic to the knowledge of that supposedly "omniscient" God of yours, is INCOMPLETE and not just that, but by this it is also INCOMPLETABLE. And I simply don't consider that to be omniscient as the only criteria for that is to be COMPLETE - knowing everything, that there is to know, including any, every and all binary sequences of 1s and 0s. But yeah, obviously your God doesn't know all of that and can't know all of that.
Do YOU consider by this criteria your God to be truly omniscient?!? Wow.
To simply put: Considering the truth of any proposition to be binary, considering the law of excluded middle no thing can be omniscinet - not even your Creator, God - as binary truth is simply in itself undecidable. There is no exception to this.
How about the following compromise, Gordon?
ReplyDeleteYou do your homework by making a (very big) paradigm shift away from that idiotic supposedly binary "infinite set of brass plates" of yours by clearly defining truth in a non-binary way and how God's knowledge is supposedly completable or is already complete in that nonbinary sense.
Otherwise I will always assume that God of yours to be not omniscient and you simply being bogus as every human Knowledge and Wisdom in the current days and age is pointing to the contrary in this binary sense of truth and how we currently understand this truth in the binary sense.
How about you doing your homework properly and not just improperly ASSUME, that there is a "Santa Claus" - capable of anything and everything? How about that?!?
"Another issue with your argument is that you seem to assume that a Turing machine can call God as a subroutine. This is not the case - Turing machines are precisely defined (this is what makes them useful in reasoning about what can and cannot be computed), and invoking God is not one of the things that Turing machines can do."
ReplyDeleteIf so, Gordon, then I guess, that we both can at least agree on the "burning in your bosom", the "witness of the Holy Spirit" and the "revelation from God" being bogus.
Sure, there are for me bogus.
Otherwise if God's truth is partially binary, then of course Turing machines can call or invoke at least God's binary truth as Turing machines can call and invoke any (finite) binary truth.
Or for what reason exactly can a Turing machine can not call or invoke or is not capable of invoking binary truths of any source?!?