Godel's incompleteness theorem and quantum theory.
In my mind, there seems to be a deep connection between quantum theory and the conclusions arrived at by Godel.
Does anyone else share this view and where can I explore this potential link further?
I already have some books in mind, such as GEB and possibly books by Penrose; but, GEB is pretty heavy stuff and unfortunately my attention span is quite limited.
Any more books I should look into for sake of curiosity and learning more about the world?
Cheers.
Does anyone else share this view and where can I explore this potential link further?
I already have some books in mind, such as GEB and possibly books by Penrose; but, GEB is pretty heavy stuff and unfortunately my attention span is quite limited.
Any more books I should look into for sake of curiosity and learning more about the world?
Cheers.
Comments (37)
It might be illuminating to discover what you think this deep connection might be, because on the face of it, there doesn't appear to be one.
Gödel's theorems are basically the discovery that most mathematical statements are undecidable. This is equivalent to Turing's discovery that almost all mathematical functions that exist logically cannot be computed by any program. The phrase "almost all" is justified by the fact that the set of all mathematical functions is uncountably infinite, whereas the set of all programs is countably infinite.
What has this got to do with quantum mechanics? Quantum mechanics seems to state, via the Bekenstein bound, that reality is a finite state machine. A FSM is finite in two ways: first that the machine has only a finite set of states is available to it, and second that its clock is digital. Time seems to be continuous, but that doesn't matter so long as the FSM cannot see this continuity, which due to QM it cannot.
Now, I'm not entirely sure about this, but it could be that because reality is a finite state machine, then the laws of nature could be expressible eventually solely in Presburger arithmetic - i.e. Gödel's theorems would have no relevance to physical reality whatsoever.
Does quantum mechanics obey causality? My intuition tells me that it does not given that physical phenomena don't obey the principle of sufficient reason under quantum mechanics. Meaning, that some events are non-localized and the distinction between localized phenomena and global phenomena gets significantly blurred.
I'll stop there for the time being as that already is a huge proposition to make...
Quantum mechanics is Unitary - which is as conservative as you can get. It is a much more stringent condition than "causality"! It is also a local theory, which has been proved. Non-local theories exist, but none of these can reproduce the predictions of quantum theory.
You claim that physical phenomena don't obey the Principle of Sufficient Reason. I think it is more accurate to claim that physicists abandon that princliple when it suits.
I'm keenly interested on this from a quasi-computational perspective, and in some sense it's a tautology. So, let me elaborate if I don't start sounding metaphysical. Given that every physical law is either computable or non computable, then within such a system there will arise situations or "state of affairs" that could not be explained within the system itself. This is basically Godel's Incompleteness theorem stated in a nutshell.
My hunch is that QM and the logical conclusions derived at by Godel are in some deep sense intertwined and manifest in reality (I mean, how can they not be... unless we're talking about higher dimensions; but, even then those higher dimensions would require another higher dimension to maintain deterministic causality of each sub-dimension).
There is no such thing as a non-computable physical law. Specifically, quantum mechanics is computable. Now, it may be the case that some non-computable aspect of Reality exists, but that would be nothing to do with QM. It would be a new physics that not only could we not express, but we could never discover. A contrary view is held by Penrose who maintains that some new physics exists, and that because it operates in the brain, humans and not computers can find it. He is an expert in QM among other things, so he knows that QM cannot provide the non-computability that you and he are looking for.
Your hunch has been proved to be wrong.
Not sure what you might consider obeying causality, and I think different interpretations will give different answers to this. But note that there do seem to be uncaused events such as excited atoms dropping to lower energy levels after indefinite duration after the excited state was introduced. Also radioactive decay seems to be uncaused. Certain interpretations assign causes to such events, and some assign full determinism yet no cause, and some interpretations assert randomness.
Interpretations aside, QM just says you can't predict these events.
Can you explore that further or point me to some sources stating that? I'd appreciate it.
Quoting noAxioms
Well, causality is intertwined with the philosophical concept of the Principle of Sufficient Reason, which basically states that everything that has a reason for happening has also a cause, with the converse being true also. Thus if QM does not obey causality then it is either beyond our capacity to understand the cause of such event or de facto QM doesn't obey causality.
See:
https://www.physicsforums.com/threads/cluster-decomposition-in-qft.547574/
I think the link is basically computability. It's not about causality.
For one thing, we have to understand that Quantum Mechanics is a way to make accurate predictions when we simply cannot use classical physics. The problem of measurement gives the link to the mathematical theorems.
And here it's useful to look at the incompleteness results not from Gödel's theorems, but something that is equivalent to it: Turings Halting problem. Now that tells us what basically an idealized Computer can compute and what it cannot. And this also gives us what basically can be computable. And ovbiously not everything can be computable. The problem? Both in Turings Halting problem and Gödel's incompleteness theorems the reason is negative self-reference, which is made so that it doesn't end up in a Paradox (as with Russell's Paradox negative self-reference does). I'll repeat: what both Gödel's incompleteness theorems and Turings Halting problem gives us is that in mathematics there basically are truths that aren't computable (or in Gödel's example, provable in the language given).
Now in Quantum Mechanics we have this problem of the measurement effecting what is measured, you have quantum entanglement, you have the uncertainty principle and wave-particle duality. Is there a link?
Well, I think so. The mathematical theorems show that in math there are limitations to what we can prove and what we can compute because of self-reference. In the particle level it seems that there would be a case for "self-reference" (with things like quantum entanglement), but basically we can overcome this by using probabilities..Yet one should note what we cannot do: calculate exactly things as we can do in classical physics.
What would it even mean for a physical law to be non-computable? Classical mechanics takes a good stab at it, achieving non-computability-in-practice. This is because of phenomena such as sensitive dependence on initial conditions, leading to chaos - two features absent in quantum mechanics. Under quantum mechanics, systems prepared in similar states will evolve in a similar way. The theory is linear.
How would you even describe a physical law that was non-computable-in-principle? How would you test it? What would it be for?
As I have mentioned already, QM via the Bekenstein bound tells us that reality is a finite state machine. Any calculation that you have ever performed, a computer has ever performed, or any finite state machine will ever perform, is expressible in Presburger arithmetic, which is consistent, compete, and decidable.
One thing is for sure: if you want non-computability, you won't find it in QM.
Non computability comes from negative self reference. Even just self-reference makes it hard make a correct working model for something.
Perhaps this is best thought about with the idea of Laplacian determinism, which is simply false even without QM. The idea of this kind of determinism goes as following:
Now why this is false is because the intellect itself a part of the universe and has an effect itself on the universe. This makes the equations a bit difficult, but it can be simply uncomputable: now put it to a situation where it's own actions define what's going to happen and counter it's forecasts, it cannot predict the future.
Yet this doesn't actually mean that the World wouldn't have causality and be deterministic, actually. It means simply that computability has it's limitations.
Well, that's Turing's Halting problem for you...
Quoting ssu
So, a computer can calculate without ordering causality? Seems fishy to me. Anyway, what about quantum wave function's? They seem to obey causality in some sense, as for computability, I don't think so...
In case anyone is interested, I posted a refined and polished version of this thread at physicsforums.
As I mentioned already, causality does not fit very well with any physical law, because they are time symmetric. According to physical law, the future causes the past just as much as the past causes the future.
Causality, whatever you mean by that word, is an abstraction, used by humans to tell stories. I think I may have mentioned that previously also. What Quantum Mechanics gives us is Unitarity. If you don't know what that means, maybe you could look it up. Information is preserved!
It would be very easy to prove me wrong about physics and computability. Simply state the physical theory that is non-computable, show how nothing can be computed from it, and perhaps indicate the point of it.
It so happens that about 30 years ago, it was proved that quantum mechanics is a computable theory.
http://www.daviddeutsch.org.uk/wp-content/deutsch85.pdf
Now, how do you prove computability when you have Godel's Theorem laying around like that?
As a hint, only the computable functions are required to express quantum mechanics. Gödel himself defined these computable (recursive) functions.
Thanks for the paper though.
http://michaelnielsen.org/blog/interesting-problems-the-church-turing-deutsch-principle/
No, I think you misunderstood.
It's not a problem of causality. Causality exists. It's a problem of computability. You can have causal relations, but something not computable..
One way of perceiving quantum uncertainty is as an incomplete process of physical manifestation. The laws of physics only go this far in deciding the fate of a particular quantum state and will just conclude it upon an observation. In this context, the laws of physics may be considered a priori and the observation a posteriori.
In Math, the a priori axiomatic system is only capable of generating certain truth (and certain falsity by negation) leaving the undecidable G-sentence out in the cold. However, by picking an appropriate model to shell the formal system, the semantic value of the G-sentence becomes accessible (though not by formal proof)..From a viewpoint inside the formal system the model is the a posteriori observation required to determine the state of the G-sentence.
I am very comfortable with this image as it connects perfectly with scenarios I developed earlier for certain chess problems in relation to Gödelian incompleteness on one side and to Quantum entanglement on another. And it emphasizes the non-existence of undefinable truth other than by random choice of model.
So you would call the world a formal system? This is part of what Gödel pointed out: There is a difference between formal deduction and existence of an entity.
Quoting Arisktotle
The sentence cannot be deduced and hence does not exist in the system.
Yes, why not?
Quoting Heiko
Could you expand on that? What do you mean by the difference here?
Quoting MindForged
Well, if the world is a formal system of sorts, then what's wrong with trying to find a link between the two?
Formal systems are by definition constructed things. They're systems of deduction we create from assumptions and derive results from using inference rules. That's nothing like reality. The problem is that the theorems are fundamentally about properties of formal systems. If that system can represent basic arithmetic, it must be either incomplete (there are truths within it which cannot be proved) or inconsistent (some contradictions can be proved). But notice, reality doesn't "represent" arithmetic. Reality is just (note: obviously philosophically controversial) the sum total of everything which is the case, it doesn't represent anything. It's not a formalism.
If there's a link between the two at all, it's only this: Quantum mechanics usually (barring quantum logic) makes use of standard mathematics (classical logic + ZFC set theory). Because of this, we are using a formal system which is necessarily incomplete, as per Godel (there are no known contradictions in standard math, so the system is incomplete). And that's it as far as I can tell. I don't see the direct connection to reality, QM isn't about mathematics but reality.
Because
Quoting Heiko
Quoting Posty McPostface
Gödel showed that there is at least one true - and hence in the sense of mathematics: existing - sentence that cannot be deduced from any set of axioms and thus not be part of any formal system.
Hence a-priori deductibility and existence are not the same.
Do you agree with @MindForged previous post for the matter?
We are talking about formal systems of symbols here. The word "symbol" already indicates representation. Formalism was more or less concerned with making "glyphs"(no better word) the kind of object mathematics deals with: "correct syntax = true statement". In mathematics - like MindForged pointed out - it seems (up to now, yet again) to be the case that correct syntax is a guarantee for a true statement. Otherwise there would be a contradiction. This has happened before and may happen again.
I'm not that much into idealism that I'd say there really must be a contradiction-free set of laws of nature as otherwise things could not happen as they do. Of course omniscience and potential omnipotence are absolutely positive so this is the only assumption one can seriously work with.
The (G-)sentence cannot be deduced and hence does not exist in the system.
That is incorrect since it is covered by the syntax of the system. It is true though that it has no semantic value and therefore does not exist as a theorem. The whole point of incompleteness is to show that the syntax of many formal systems is "bigger" than their semantics. The Gödel-sentence would never have been debated had it been excluded a priori by the syntax-checker of the active system.
That is one of the interesting points of the chess rules (notably their extensions in the Codex conventions). Illegal positions - not axiomatically derivable from the game starting position - are not permitted to be associated with a semantic value for "winnability" though this is often possible. The chess community decided to declare these positions syntactically illegal even where a lot of analysis is required to prove this point. Note that chess is more complicated than common mathematical examples as it contains a separate geometric syntax layer for the placing of chess units on the board.
Your comment would hold in chess where illegal positions would be syntactically placed outside the evaluation system for winnability.
This is incorrect since the sentence exists in the syntax of the system. It is true though that it does not have a semantic value and therefore does not exist as a theorem. The whole point of incompleteness is to show that the syntax of many formal systems is "bigger" than their semantics.
The point of my original comment is however metaphorical. It describes what a human being living inside a formal system would need to make sense of the syntactically present G-sentence. Could he read into the model associated with the system - as a contingent truth not as a necessary one - he could perceive its semantic value in the same way he could for a quantum state in our physical reality by making an observation.
What do you mean by omniscience and potential omnipotence? I take it from a Platonic POV and assume that math is the apparent reality, therefore what does that imply according to Godel's Incompleteness Theorems?
Quoting Arisktotle
Oh... the syntax was a metaphor. "2=3" ain't true either and looks like some equation nontheless. When using "syntax" in the sense I did this does not mean " 'Number = Number' is a valid expression ". One can easily write a computer-program that could deduce any valid a+b=c for natural numbers gramatically.
N := 1 | s(N) for example defines the natural numbers inductively.
This is the whole point. It's a pitty but it seems we cannot just type in some axioms and let the computer do for a while to get all true statements (aside from time-consumption, of course). This would have been formalism in it's pure form.
Quoting Arisktotle
It is not true in the formal system as it cannot be deduced.
If it was true in the system then the system would be self-contradictory.
Either incomplete or self-contradictory. It was the mathematicians taking a look at Gödel's proof who thought the sentence was true.
The ability to understand and maybe manipulate the world without limitation.
Quoting Posty McPostface
I do not understand. There is math and there is... stones. How are stones math?
If it was true in the system then the system would be self-contradictory.
Either incomplete or self-contradictory. It was the mathematicians taking a look at Gödel's proof who thought the sentence was true.
Sorry my original message mysteriously disappeared after I edited out a comma and not having saved it I replaced it with a simpler one. Contains the essentials though.
I am not sure of the source, but I am sure I read that Kurt Gödel himself believed the G-sentence to be true outside the system. It didn't matter for his incompleteness theorems as they only depend on "undecidability" which is obviously a weaker proposition.
Modern mathematics holds the view that the G-sentence is true in some models (notably the standard model) and false in others. I view it as an information problem. Since some essential "reflective" information was not passed on from the model to the formal system, it couldn't decide the outcome. Then again, formal systems actually lack the tool required to receive that information and we would have to conclude that Gödels concept simply cannot be completely coded into the language of the formal system. Which means that mathematical logic halted around the age of 4 for a human child. Therefore I am not overly impressed when a mathematician speaks of "undefinable truth".
Who? Which model?
Quoting Arisktotle
Again: Which model?
Quoting Arisktotle
No, no... The sentence could be coded into the all-system. It just blew up then.
Would a definition be true in respect to itself?
Modern mathematics holds the view that the G-sentence is true in some models (notably the standard model) and false in others.
— Arisktotle
Who? Which model?
From Wikipedia, Gödels incompleteness theorems:
Although the Gödel sentence of a consistent theory is true as a statement about the intended interpretation of arithmetic, the Gödel sentence will be false in some nonstandard models of arithmetic, as a consequence of Gödel's completeness theorem (Franzén 2005, p. 135). That theorem shows that, when a sentence is independent of a theory, the theory will have models in which the sentence is true and models in which the sentence is false. As described earlier, the Gödel sentence of a system F is an arithmetical statement which claims that no number exists with a particular property. The incompleteness theorem shows that this claim will be independent of the system F, and the truth of the Gödel sentence follows from the fact that no standard natural number has the property in question. Any model in which the Gödel sentence is false must contain some element which satisfies the property within that model. Such a model must be "nonstandard" – it must contain elements that do not correspond to any standard natural number (Raatikainen 2015, Franzén 2005, p. 135).
Since some essential "reflective" information was not passed on from the model to the formal system, it couldn't decide the outcome.
— Arisktotle
Again: Which model?
Then again, formal systems actually lack the tool required to receive that information and we would have to conclude that Gödels concept simply cannot be completely coded into the language of the formal system.
— Arisktotle
No, no... The sentence could be coded into the all-system. It just blew up then.
Note that the latter citations constitute my view as indicated in the comment. This is not standard mathematical stuff but something I have been working on for a while. For instance, I doubt the all-system will be capable of handling new definitions for function domains and co-domains necessary to be compatible with mature human logic.
Those are indeed interesting as the G-sentence could be put onto an island for it's own without any connection to the rest of the world, like: "There is everything that is the case. And then there is the G-sentence."
Meanwhile some visitors may choose to continue this thread in accordance with its original intention to link up Quantum Theory and Incompleteness from which we got a bit sidetracked.