24
$\begingroup$

Do Gödel's incompleteness theorems have any significance or application to axiomatic theories of classical mechanics like Newton's for example?

$\endgroup$
7
  • $\begingroup$ I don't know, but the only "undecidable statements" I've ever heard of were self-referential. That is, a statement expressed in the language of some formal system, that describes a statement expressed in the same formal system, that happens to be itself. The whole point of classical mechanics is to describe the physical world. Would it even make sense to talk about a statement of classical mechanics that describes a statement of classical mechanics instead of describing some physical system? $\endgroup$ Feb 7, 2020 at 15:39
  • 3
    $\begingroup$ @SolomonSlow - The trick is to encode the classical mechanics statement plus classical mechanics in a formal system that is then implemented using a classical mechanics system. A very contrived situation, surely, but totally allowed. $\endgroup$ Feb 7, 2020 at 15:45
  • 1
    $\begingroup$ Related: physics.stackexchange.com/q/14939/2451 and links therein. $\endgroup$
    – Qmechanic
    Feb 7, 2020 at 16:44
  • 1
    $\begingroup$ Backreaction, Monday, February 03, 2020 Guest Post: “Undecidability, Uncomputability and the Unity of Physics. Part 1.” by Tim Palmer $\endgroup$ Feb 7, 2020 at 22:44
  • 1
    $\begingroup$ physics.stackexchange.com/questions/403574/… is related. $\endgroup$ Feb 8, 2020 at 23:47

4 Answers 4

22
$\begingroup$

Yes. One simple (trivial) way of seeing it is to consider a mechanical computer, and ask whether one can predict its end-state given the initial state without running it. Since this is exactly the Turing halting problem, any method that would allow you to make that prediction in Newtonian mechanics would either be a counterexample to the theorem (contradiction), or require some uncomputable element.

This should not be surprising. Chaotic dynamical systems lack analytic solutions and are often undecidable. This appears to be true (one needs to define deciding carefully here) for the N-body problem (see also this dissertation).

Does this matter? Probably less to physicists and more the philosophers and computer scientists. The issue of how computation is embodied in the physical world is a big topic, with interesting questions about whether hypercomputation is possible for real (it is allowed in Newtonian mechanics - one can in principle solve the halting problem using a Newtonian configuration) and whether physical laws are prognostic.

$\endgroup$
17
  • 3
    $\begingroup$ I am not sure if the "undecidability" in Gödel, and in Turing means the same. $\endgroup$
    – peterh
    Feb 8, 2020 at 1:43
  • 1
    $\begingroup$ @peterh-ReinstateMonica I believe the Curry-Howard correspondence implies they are the same. Given a mathematical proposition, build a Turing machine that outputs 1 if it is a theorem and 0 if it is a non-theorem. If it is undecidable, then it cannot output anything, and thus, it must not halt. Not rigorous, but I think that's the gist of it. en.wikipedia.org/wiki/Curry%E2%80%93Howard_correspondence $\endgroup$ Feb 8, 2020 at 3:52
  • 6
    $\begingroup$ I cannot agree with this answer since the Halting problem is intimately tied to the unbounded nature of Turing machines, whereas any physical computer would have to be bounded and therefore be computationally equivalent to a finite automaton, for which halting can be determined. $\endgroup$
    – kviiri
    Feb 8, 2020 at 9:39
  • 1
    $\begingroup$ @kviiri Why would a physical computer have to be bounded? $\endgroup$
    – JiK
    Feb 8, 2020 at 13:22
  • 6
    $\begingroup$ Note that the question was about Newtonian mechanics, not about standard physics. Infinite numbers of particles and arbitrarily high momenta are definitely allowed in the formalism. $\endgroup$ Feb 8, 2020 at 15:41
4
$\begingroup$

The theorem does have consequences for any formal system that includes arithmetic. There will always be theorems that will be undecidable. Those theorems though, always involve infinite quantities, one example is: Do this system of Diophantine equations have a finite or infinite number of solutions?". The problem is in general undecidable, although for particular examples you might find it decidable. Other more interesting examples can be found here, and also in @Anders Sanberg's answer

$\endgroup$
4
$\begingroup$

I would like to share two examples that one could consider a "physics version" of Gödel's incompleteness theorem. This will not really answer the question about whether axiom systems in physics can be formally incomplete in the Gödel sense. However, it will show how an incompleteness of a physical theory is usually connected to some physical insight that is not captured by the axiom system, and that a mathematical incompleteness would therefore simply indicate that our theory does not describe all the physics. (This argument assumes determinism, but since the question is about classical mechanics I think that is fair).


The first example is Newton's cradle, or a simplified version where three perfectly incompressible identical spheres are lined up perfectly in space and collide along a line. Pictorially (o = sphere, o> = is moving sphere, -=spatial separation):

--o>---o---o---

From an axiomatic perspective, we have Newton's laws (mainly momentum conservation relevant here) and the perfectly incompressible sphere assumption (which gives energy conservation).

For two balls (--o>----o--), the problem is solved by momentum and energy conservation and one finds that the first ball stops while the second ball takes over the momentum of the first one. There is no problem here.

For three balls (--o>----o----o---), the problem is simply a succession of two ball collision.

The problem becomes interesting when two of the balls touch at the start (--o>---oo----). When setting up momentum and energy conservation for this system, one finds that the equations have multiple physical solutions, with the two successive two-ball collision solution only being one of them. In some sense, the problem is undecidable within our "axiom system".

What is happening here? The answer is very simple: The perfectly incompressible sphere assumption does not make much sense when two balls touch. In reality, even if the balls are in a limiting sense perfectly incompressible, there will be show waves travelling through the material and cause a unique trajectory to be realized physically. Our axioms do not capture this situation.


Another set of famous examples are various paradoxes in special relativity (e.g. the ladder paradox), which in the end require the concept of a perfect rigid body to be abandoned.


The Newton's cradle example is undecidable in a physics sense. In a mathematical sense, this has, however, nothing to do with Gödel's incompleteness theorem. The special relativity paradoxes are an example of axioms that physically do not go together.

$\endgroup$
3
  • 1
    $\begingroup$ Nice example (+1). Although it seems that all apparently Goedel-like, undecidable, situations in physics, become decidable when one properly insert back physical limitations (like, no perfect elastic body, no perfect rigid,..) $\endgroup$
    – lcv
    Feb 8, 2020 at 13:57
  • 3
    $\begingroup$ I do not think that "having multiple solutions" is in any sense the same as the problem being undecidable. In the case of multiple solutions we have solved the problem, it's just that its solution is not unique. In the case of undecidability we have proven that it is impossible to arrive at a general solution at all.. $\endgroup$
    – ACuriousMind
    Feb 8, 2020 at 16:48
  • $\begingroup$ @ACuriousMind Depends on what you mean by "the problem". If you want to know what happens physically, the considered axiom system does not answer the question. I am aware that this is by no means the same as undecidability in Gödel's sense and I specified that in my answer. My point is that investigating Gödel theorems for physics theories is only useful in a limited sense, since an incompleteness is inherently unphysical. Any suggestions to make that clearer in my answer? $\endgroup$ Feb 8, 2020 at 19:54
1
$\begingroup$

If you are being strict about the kinds of things Gödel was talking about, no. Godel was operating on systems which could prove all true statement in arithmetic. In physics these are generally statements that are assumed rather than proven. Physics builds on top of math, building upon what mathematics asserts to be true.

To start off, you would need to find something quantized in classical mechanics. Most classical mechanics topics deal with real numbers, and thus most meaningful statements are proven using Second Order Logic(SOL). Gödel demonstrated that SOL systems cannot admit a proof of their own consistency, but beyond that he has little to say about such systems.

You woudl also need to find a quantized self-referential system, and then one which admits something akin to a proof of its own consistency.

Indeed, true self reference itself is quite rare in physics, and a bit of a novelty. But you may be able to find something to sink your teeth into in the world of trying to model how the brain thinks. But the more we learn about the brain, the more we learn how little of it relies on something as brittle as logic.

$\endgroup$
9
  • $\begingroup$ That's just not really true. Incompleteness theorem applies for any formal system that contains arithmetic. Ultimately whatever the deductive system you use in physics you should be able to find undecidable statements. $\endgroup$
    – Kugutsu-o
    Feb 9, 2020 at 9:11
  • $\begingroup$ I think any formal system that contains arithmetic is self referential by default $\endgroup$
    – Kugutsu-o
    Feb 9, 2020 at 9:23
  • $\begingroup$ @Ezio I believe that true arithmetic is a formal system which is complete and consistent. It, of course, its not effectively generated. This does bring up a funny quirk of the question. If the systems physicists look at do not strive to meet the very specific requirements on the systems Godel was making proofs about, does that mean they are affected or unaffected by his theorems? $\endgroup$
    – Cort Ammon
    Feb 9, 2020 at 15:06
  • $\begingroup$ I don't think it's a matter of belief. Im not sure how affected physics axiomatic systems are this is the question. $\endgroup$
    – Kugutsu-o
    Feb 9, 2020 at 19:31
  • $\begingroup$ @Ezio Well, at the heart of physics is the fundamental philosophical question of science. Are we discovering fundamental laws of physics, or are we identifying patterns we see everywhere we look? The latter is completely immune to Godelian thinking in every way, because it isn't seeking to prove things. $\endgroup$
    – Cort Ammon
    Feb 11, 2020 at 3:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.