I'm no expert on Godel's theorems, but most of them seemed to apply to a straight deterministic single thread model with no quantum probability, Incompleteness holds. A system still cannot predict itself via simulation. Quantum indeterminacy does make it worse of course. Or possibly better. There are claims that quantum computers work outside the limits assumed by Godel, but such a quantum computer, if possible, still cannot predict 'the future' because there would be no unique answer to supply.

In my mind, there seems to be a deep connection between quantum theory and the conclusions arrived at by Godel. — Question

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.

Well, before I start spouting nonsense, let me ask some a question.

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

Does causality exist in any fundamental physical theory, or is an abstraction used by humans to tell stories? Fundamental theories are time-symmetric so work just as well forwards or backwards in time.

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.

Well, causality in scientific terms is what I understand as a deterministic system.

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

Well, as I mentioned, you have Unitarity, which is an especially restrictive form of determinism. Even black-holes cannot destroy information!

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.

Does quantum mechanics obey causality? — Question

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.

There is no such thing as a non-computable physical law. — tom

Can you explore that further or point me to some sources stating that? I'd appreciate it.

Not sure what you might consider obeying causality, and I think different interpretations will give different answers to this. — 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/

What would be the link between the two? Sort of, I would say, but not 100%.

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.

There is no such thing as a non-computable physical law. — tom


Can you explore that further or point me to some sources stating that? I'd appreciate it. — Question

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.

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 — tom

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:

We may regard the present state of the universe as the effect of its past and the cause of its future. An intellect which at a certain moment would know all forces that set nature in motion, and all positions of all items of which nature is composed, if this intellect were also vast enough to submit these data to analysis, it would embrace in a single formula the movements of the greatest bodies of the universe and those of the tiniest atom; for such an intellect nothing would be uncertain and the future just like the past would be present before its eyes.

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.

What would it even mean for a physical law to be non-computable? — tom

Well, that's Turing's Halting problem for you...

I think the link is basically computability. It's not about causality. — 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.

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 — Question

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

Fine, substitute causal with computable/deterministic.

Now, how do you prove computability when you have Godel's Theorem laying around like that?

It has been PROVED that quantum mechanics is computable - read the paper!

As a hint, only the computable functions are required to express quantum mechanics. Gödel himself defined these computable (recursive) functions.

I wasn't only talking about QM in my previous post; but, all of the mathematics involved in describing the universe.

Thanks for the paper though.

Michael Nielsen wrote the standard book on quantum computing. Here's his take on computability.

http://michaelnielsen.org/blog/interesting-problems-the-church-turing-deutsch-principle/

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... — Question

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

I pondered on the relationship between QM and Gödelian incompleteness a while ago and found some interesting parallels especially to the G-sentence. What comes to mind straight away is the similarity of quantum state uncertainty and undecidability of the G-sentence which is probably what made you look for a deep connection in the first place.

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.

In my mind, there seems to be a deep connection between quantum theory and the conclusions arrived at by Godel. — Posty McPostface

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.

From a viewpoint inside the formal system the model is the a posteriori observation required to determine the state of the G-sentence. — Arisktotle

The sentence cannot be deduced and hence does not exist in the system.

Godel's theorems only apply to formal systems, as per Godel. For any formal system capable of representing basic arithmetic, we can prove the the Godel sentence "This sentence is unprovable" from within that formal system. So whenever I hear people try to connect it to reality or the human mind or whatever, I immediately frown. It's a metamathematical result, that's really it.

So you would call the world a formal system? — Heiko

Yes, why not?

This is part of what Gödel pointed out: There is a difference between formal deduction and existence of an entity. — Heiko

Could you expand on that? What do you mean by the difference here?

Godel's theorems only apply to formal systems, as per Godel. — MindForged

Well, if the world is a formal system of sorts, then what's wrong with trying to find a link between the two?

Well, if the world is a formal system of sorts, then what's wrong with trying to find a link between the two? — Posty McPostface

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.

Yes, why not? — Posty McPostface

Because

This is part of what Gödel pointed out: There is a difference between formal deduction and existence of an entity. — Heiko

Could you expand on that? What do you mean by the difference here? — 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?

Do you agree with MindForged previous post for the matter? — Posty McPostface

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.

The (G-)sentence cannot be deduced and hence does not exist in the system.

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.

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. — Heiko

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?

That is incorrect since it is covered by the syntax of the system. — Arisktotle

The Gödel-sentence would never have been debated, would it have been excluded a priori by the syntax-checker of the active system. — 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.

It is true though that it has no semantic value and therefore does not exist as a theorem. — 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.