The celebrated results of Gödel and Turing showed that there are apparently simple questions that cannot be answered, even in principle. Their results revolutionised mathematics and laid the foundations for computing. But they have arguably had less impact in physics. Most undecidable problems are abstract mathematical questions, not questions of direct concern to physics. Are there simple physical properties and quantities that are fundamentally undecidable or uncomputable?
We aim to investigate the fundamental limits on our knowledge and understanding of the physical world, with an emphasis on quantum systems. We will focus on properties that emerge from simple microscopic laws in the asymptotic limit. These limits are ubiquitous in statistical physics as well as in information theory - fields whose mathematical bases have much in common. Examples include phases of matter and their corresponding material properties (in statistical physics), or capacities for information transmission (in information theory). We aim to show that several such natural physical properties are not provable or computable from the underlying "microscopic" laws. To achieve this, we will use recent methods from quantum information theory to connect physics with the ideas of Gödel and Turing. At the same time we will approach the subject from the other "provable" end and thereby identify the border between what is and what is not provable or computable as precisely as possible.
