[ozb]

Godel's proof relies on the self-referential nature of the Godel sentence; without that, his theorem does not apply. Generally you need arithmetic, but also (something equivalently expressive to) universal quantification. Physical theories do not need to include that.

Note Godel's proof is mechanically exactly analogous to Turing's proof of the undecidability of the halting problem, because ultimately it's the same thing (Curry-Howard, Prolog, and all that). So you can bypass arithmetic, but you can't really bypass self-reference; just like programming languages need some looping or recursion (or equivalent expressiveness) to be Turing-complete, mathematical theories need universal quantification to be subject to Godel's Incompleteness Theorem.

Of course, you can have a physical theory that _is_ Turing-complete, say the Newtonian billiard ball model (and, y'know, we can build computers); but that doesn't mean the theory will necessarily tell you, as a static, measureable physical fact, whether a particular physical process (say, an n-body system) will ever halt or loop, or go on forever with ever-increasing complexity; so you could (in principle, in Newtonian mechanics) build some (mechanical!) physical system that simulates the Goldbach conjecture, or looks for solutions to an arbitrary Diophantine equation, but if there are no integer solutions you'll never actually be able to show it; the theory is incomplete in the mathematical sense, but just as complete a description of reality's rules.

[mxkopy]

They have some explicit examples of physics explainable by quantum gravity that resolve but are undecidable, n-body thermalization being one. Of course that’s given a sort of hand wavey understanding of quantum gravity, I guess one that they say should tell us whether a system thermalizes.

EDIT: I should also mention the idea that reality can tell us if a statement about a theory is true, given that the theory is an accurate description of reality. So if there’s an accurate Turing complete theory of reality, and we see some process that’s supposed to encode a decision on an undecidable statement being resolved (I guess in a non-probabilistic way as well), then we can conclude that reality is deciding undecidable statements in some nontrivial way.

[ozb]

Note that in general, a physical instantiation of an undecidable problem must be specified/realized to _infinite_ precision; that is, for any such system S, and for any eps>0, there is a perturbation p with distance d<eps (eg, move a billiard ball an arbitrarily small amount) that is provable; this is analogous to the fact that existence of solutions to Diophantine equations is undecidable, but the theory of real closed fields is decidable, which means that the only undecidable case is when an equation has solutions _arbitrarily close_ to integers, but never quite an integer. I am not a physicist, but I don't believe any physics actually cares about infinitely-precise setups.