Are physical laws uncomputable in any type of computation (according to this article)?

It seems that this article (https://arxiv.org/pdf/1312.4456.pdf) proposes that laws of physics are uncomputable (i.e., they could not be reproduced on a computer), but I'm not sure about it.

In some part of the article it says:

If we expand the set of computational devices that we use to define computational complexity, then the consequences of the known laws of physics can in principle be elaborated in polynomical [sic] time on classical and quantum computers.

If we restrict our attention to laws whose consequences can be evaluated in polynomial time, then the problem of finding concise expressions of physical laws is no longer uncomputable.

So, what is it saying? That laws of physics are uncomputable? That laws of physics could not be reproduced in a computer? That laws of physics could not be reproduced in any type of computer?

Also, in the conclusions it says:

This chapter reviewed how uncomputability impacts the laws of physics. Although uncomputability as in the halting problem arises from seemingly esoteric logical paradoxes, I showed that common and basic questions in physics have answers that are uncomputable. Many physical systems are capable of universal computation: to solve the question of whether such a system has discrete or continuous spectrum in a particular regime, or whether it is gapped or gapless, requires one to solve the halting problem. At a more general level one can think of the all scientific laws as providing concise, easily unpacked descriptions of obserbational [sic] and experimental data. The problem of finding the most concise description of a data set is uncomputable in general, and the problem of finding the most concise description whose predictions are easily evaluated is NP-complete.

So, what can we conclude from this? Also, what does it exactly mean that "finding the most concise description whose predictions are easily evaluated is NP-complete"?

• It seems the author is referring strictly to the uncomputability of (maximally) concise expressions of physical laws. Well, of course that is uncomputable; it is a pretty basic result in Kolmogorov complexity. Whether this implies the laws of physics themselves are "uncomputable" (in whatever sense this should be interpreted) is debatable. – dkaeae Dec 21 '18 at 13:26
• Please keep in mind that papers on arXiv are not peer reviewed and that just about anybody can post anything they want there. Caveat emptor. – Andrej Bauer Dec 22 '18 at 9:12
• Adding to @Andrej Bauer's comment, note the paper was not even properly spell-checked given the multiple (trivial) spelling errors in the excerpts cited. – dkaeae Dec 22 '18 at 9:29

1 Answer

The reasoning given in the paper is too vague to be of much value. The question whether laws of physics are computable cannot be decided by a philosophical discussion. It already takes some hard physics and math to even properly formulate the question.

Let me give an analogy. It is impossible to travel faster than light, right? But if I shine a laser at the moon and move it fast enough, the laser dot on the moon will move faster than light. So how is this possible? We have a contradiction in physics. Or do we?

It is easy to have a discussion about computability in the real world, or computability of the laws of physics, at the level of the previous paragraph. For instance, the very nice and seriously presented result on the Undecidability of the spectral gap is easy to misinterpret, because the devil is in the details. The actual experiment cannot be set up because it requires unrealistic conditions. If we approximate the experiment, then the theorem does not hold anymore. But this does not stop people from misinterpreting the result.

For a more reasonable account of computability of the laws of physics I recommend A computable universe, in which you can find discussions of many aspects of computability. If you are interested in computability of the laws of physics then the Matthew Szudzik's contribution The Computable Universe Hypothesis.

Personally I would say that the question "is the universe computable" is ill-formed, because this is not a falsifiable statement. The question "are the laws of physics computable" makes more sense, but one really has to be careful how it is phrased.