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