Some questions are hard because we have not yet found the right method. Others are hard in a deeper sense: no algorithm can solve them in full generality. This idea, known as undecidability, began in mathematics and computer science with the work of Gödel, Church, and Turing. It shows that even with perfect logic and unlimited patience, there are well-defined questions for which no universal step-by-step procedure can always give an answer. Surprisingly, such limits do not remain confined to abstract mathematics. They can also appear in physics, where one asks whether a material has a certain phase, whether a system eventually settles down, or whether a quantum device can exhibit a particular behaviour.
This review explains how undecidability has entered modern physics, especially through many-body systems and quantum information theory. It traces the history from early mathematical ideas to recent results showing that some apparently physical questions can encode the logic of computation itself. In such cases, predicting the behaviour of a physical system can become as impossible as solving the halting problem for a computer program. The review does not suggest that everyday experiments are beyond science; rather, it clarifies the precise frontier between what physics can in principle predict algorithmically and where fundamental computational barriers arise. In doing so, it provides an accessible map of a growing field at the boundary of physics, mathematics, and computation.
Undecidability in Physics: A Review
Álvaro Perales-Eceiza, Toby Cubitt, Mile Gu, David Pérez-García, and Michael M. Wolf
Physics Reports 1138, 1–29
