You will never be able to prove every mathematical truth. For me, this incompleteness theorem, discovered by Kurt Gödel, is one of the most incredible results in mathematics. It may not surprise everyone—there are all sorts of unprovable things in everyday life—but for mathematicians, this idea was a shock. After all, they can construct their own world from a few basic building blocks, the so-called axioms. Only the rules they have created apply there, and all truths are made up of these basic building blocks and the corresponding rules. If you find the right framework, experts long believed, you should therefore be able to prove every truth in some way.
But in 1931 Gödel demonstrated otherwise. There will always be truths that elude the basic mathematical framework and are impossible to prove. And this is not a purely abstract finding, without implications for practical situations. Shortly after Gödel’s groundbreaking work, the first provably unprovable problems emerged. For example, it will never be possible to clarify how many real numbers exist within the mathematical framework currently in use. And unsolvable problems are not limited to mathematics. For example, in certain card and computer games (such as Magic: The Gathering), situations can arise for which it is impossible to determine which player will win. And in physics, it is not always possible to predict whether a crystal system will conduct electricity.
Now experts, including physicist Toby Cubitt of University College London, have found another way in which the incompleteness theorem is reflected in physics. They have described a particle system that undergoes a phase transition—a change similar to the shift when water freezes below a temperature of zero degrees Celsius. But the critical parameter at which the phase transition occurs for this system of particles cannot be calculated, unlike that of water. “Our result ... illustrates how uncomputable numbers may manifest in physical systems,” write the physicists in a preprint paper posted last month on the server arXiv.org.
On supporting science journalism
If you're enjoying this article, consider supporting our award-winning journalism by subscribing. By purchasing a subscription you are helping to ensure the future of impactful stories about the discoveries and ideas shaping our world today.
An Indeterminable Phase Transition
This is not the first time that experts have encountered an unpredictable phase transition. Back in 2021 Cubitt and two of his colleagues described another physical system whose transitions are unpredictable. In that case there were an infinite number of phase transitions possible, however. Such situations do not occur in nature. The researchers therefore asked themselves whether unpredictability can ever occur in realistic systems.
In the new work, Cubitt and his colleagues investigated a fairly simple system: a finite square lattice containing an arrangement of several particles that each interact with their nearest neighbor. Such models are usually used to describe solids. This is because their atoms are arranged in a regular structure, and their electrons can interact with those of the immediately surrounding atoms. In Cubitt’s model, the strength of the interaction between the electrons depends on a parameter φ—the greater φ is, the more strongly the particles in the atomic shells repel each other.
If the repulsion φ is small, the outer electrons are mobile: they can jump back and forth between the atomic nuclei. The stronger φ is, the more the electrons freeze in their place. This different behavior is also reflected in the energy of the system. You can look at the ground state (the lowest total energy) and the next highest energy state. If φ is very small, the total energy of the system can grow continuously. As a result, the system conducts electricity without any problems. For large values of φ, however, the situation is different. With such values, the energy only increases gradually. There is a gap between the ground state and the first excited state. In this case—depending on the size of the gap—the system would be a semiconductor or an insulator.
To date, physicists have created thousands of similar models to describe all kinds of solids and crystals. But because the system presented by Cubitt and his colleagues exhibits two different behaviors, there must be a transition between the conducting and the insulating phase. In other words, there is a value of φ above which the energy spectrum of the system suddenly has a gap.
An Incalculable Number
Cubitt and his team have determined the value of φ at which this gap occurs. And it corresponds to the so-called Chaitin constant Ω—a number that may sound familiar to math nerds because it is among the few known examples of numbers that cannot be calculated. These are irrational numbers whose decimal places continue forever and never repeat regularly. In contrast to computable irrational numbers such as π or e, however, the value of a noncomputable number cannot be approximated with arbitrary precision. There is no algorithm that, if it runs for infinitely long, outputs Ω. If Ω cannot be calculated, then it is also not possible to specify when a phase transition occurs in the system studied by Cubitt and his colleagues.
Argentine-American mathematician Gregory Chaitin defined Ω precisely for the purpose of finding a noncalculable number. To do this, he used the famous halting problem from computer science: according to it, there is no machine that can judge, for all possible algorithms, whether a computer executing them will come to a halt at some point or not. If you give a computer any algorithm, it may be possible to judge whether that algorithm can be executed in a finite time. But there is demonstrably no method that can do this for all conceivable program codes. The halting problem is therefore also a direct application of Gödel’s incompleteness theorem.
The Chaitin constant Ω corresponds to the probability with which the theoretical model of a computer (a Turing machine) halts for any given input:
In this equation p denotes all programs that halt after a finite runtime, and |p| describes the length of the program in bits. In order to calculate the Chaitin constant exactly, you would have to know which programs hold and which do not—which is not possible, according to the holding problem. Although in 2000 mathematician Cristian Calude and his colleagues succeeded in calculating the first several digits of the Chaitin constant, 0.0157499939956247687..., it will never be possible to find all decimal places.
Cubitt’s team has therefore been able to prove mathematically that his physical model undergoes a phase transition for a value of φ = Ω: it goes from being a conductor to an insulator. Because Ω cannot be calculated exactly, however, the phase diagram of the physical system is also undefined. To be clear, this has nothing to do with the fact that current computers are not powerful enough or that there is not enough time to solve the problem—the task is demonstrably unsolvable. “Our results illustrate uncomputable numbers may emerge as phase transition points in physics-like models, even when all underlying, microscopic data are fully computable,” the physicists write in their paper.
Technically the precision with which the Chaitin constant can be specified makes it sufficient for real-world applications. But the work by Cubitt and his colleagues still illustrates once again how incredibly far-reaching Gödel’s insight is. Even after more than 90 years, there are still new examples of unprovable statements. It’s probable that far-reaching physical problems, such as the search for a theory of everything, are affected by Gödel’s incompleteness theorems.
This article originally appeared in Spektrum der Wissenschaft and was reproduced with permission.