Nature, 09 December 2015
Kurt Gödel (left) demonstrated that some mathematical statements are undecidable; Alan Turing (right) connected that proof to unresolvable algorithms in computer science.
A logical paradox at the heart of mathematics and computer science turns out to have implications for the real world, making a basic question about matter fundamentally unanswerable.
In 1931, Austrian-born mathematician Kurt Gödel shook the academic world when he announced that some statements are ‘undecidable’, meaning that it is impossible to prove them either true or false. Three researchers have now found that the same principle makes it impossible to calculate an important property of a material — the gaps between the lowest energy levels of its electrons — from an idealized model of its atoms.
The result also raises the possibility that a related problem in particle physics — which has a US$1-million prize attached to it — could be similarly unsolvable, says Toby Cubitt, a quantum-information theorist at University College London and one of the authors of the study.
The finding, published on 9 December in Nature, and in a longer, 140-page version on the arXiv preprint server, is “genuinely shocking, and probably a big surprise for almost everybody working on condensed-matter theory”, says Christian Gogolin, a quantum information theorist at the Institute of Photonic Sciences in Barcelona, Spain.
From logic to physics
Gödel’s finding was first connected to the physical world in 1936, by British mathematician Alan Turing. “Turing thought more clearly about the relationship between physics and logic than Gödel did,” says Rebecca Goldstein, a US author who has written a biography of Gödel.
Turing reformulated Gödel’s result in terms of algorithms executed by an idealized computer that can read or write one bit at a time. He showed that there are some algorithms that are undecidable by such a ‘Turing machine’: that is, it’s impossible to tell whether the machine could complete the calculations in a finite amount of time. And there is no general test to see whether any particular algorithm is undecidable. The same restrictions apply to real computers, since any such devices are mathematically equivalent to a Turing machine.
Since the 1990s, theoretical physicists have tried to embody Turing’s work in idealized models of physical phenomena. But “the undecidable questions that they spawned did not directly correspond to concrete problems that physicists are interested in”, says Markus Müller, a theoretical physicist at Western University in London, Canada, who published one such model with Gogolin and another collaborator in 2012.
“I think it’s fair to say that ours is the first undecidability result for a major physics problem that people would really try to solve,” says Cubitt.
Cubitt and his collaborators focused on calculating the ‘spectral gap’: the gap between the lowest energy level that electrons can occupy in a material, and the next one up. This determines some of a material’s basic properties. In some materials, for example, lowering the temperature causes the gap to close, which leads the material to become a superconductor.
The team started with a theoretical model of a material: an infinite 2D crystal lattice of atoms. The quantum states of the atoms in the lattice embody a Turing machine, containing the information for each step of a computation to find the material’s spectral gap.
Cubitt and his colleagues showed that for an infinite lattice, it is impossible to know whether the computation ends, so that the question of whether the gap exists remains undecidable.
For a finite chunk of 2D lattice, however, the computation always ends in a finite time, leading to a definite answer. At first sight, therefore, the result would seem to have little relation to the real world. Real materials are always finite, and their properties can be measured experimentally or simulated by computer.
But the undecidability ‘at infinity’ means that even if the spectral gap is known for a certain finite-size lattice, it could change abruptly — from gapless to gapped or vice versa — when the size increases, even by just a single extra atom. And because it is “provably impossible” to predict when — or if — it will do so, Cubitt says, it will be difficult to draw general conclusions from experiments or simulations.
Cubitt says that the team ultimately wants to study a related problem in particle physics called the Yang–Mills mass-gap problem, which the Clay Mathematics Institute in Peterborough, New Hampshire, has named one of its Millennium Prize Problems. The institute is offering $1 million to anyone who is able to solve it.
The mass-gap problem relates to the observation that the particles that carry the weak and strong nuclear force have mass. This is also why the weak and strong nuclear forces have limited range, unlike gravity and electromagnetism, and why quarks are only found as part of composite particles such as protons or neutrons, never in isolation. The problem is that there is no rigorous mathematical theory which explains why the force-carriers have mass, when photons, the carriers of the electromagnetic force, are massless.
Cubitt hopes that eventually, his team’s methods and ideas will show that the Yang–Mills mass-gap problem is undecidable. But at the moment it doesn’t seem obvious how to do it, he says. “We’re a long way from winning the $1 million.”
Nature | doi:10.1038/nature.2015.18983