# Computability of physics

As far as I understand a Universal Quantum Simulator can simulate any quantum system and thus anything that exists in the universe. Also, a quantum computer can implement such a quantum simulator. Further, from what I've read, a quantum computer does not have the ability to compute something that is not computable by a classical Turing Machine, although it can perform certain computations much more efficiently.

However, I recently saw this: Classical problem becomes undecidable in a quantum setting. The actual paper: Quantum measurement occurrence is undecidable

I don't understand this, unfortunately, so I wanted to ask, does this mean that physics is not computable by a classical computer (Turing Machine)? What about by a quantum computer? Or is this article saying something different altogether?

-
The preprint is freely available: arxiv.org/abs/1111.3965 . – Johannes Feb 25 '13 at 14:40

There is a difference between being able to run a program (Turing machine) and being able to decide whether that program evenutally finishes running. The latter is called a $\Pi_1$ decision problem.