Rocky Acosta / CC BY 3.0
A common math problem is whether a Turing machine will complete a program in a finite time.
In physics, the spectral gap is the difference in energy between a material in the ground state and in the first excited energy state. A material is known as “gapped” if the difference in energy can be bounded below — in other words, if the difference is large — and “gapless” if the difference is small.
The spectral gap is important to understanding a material’s quantum phase behavior. A quantum phase transition — which can be thought of as similar to a thermal phase transition, where matter transitions from solid to liquid, for example — can occur at zero temperature if a material is gapless. Therefore, studying the spectral gap of different materials is an important research question in physics.
Recently, mathematicians Toby Cubitt, David Perez-Garcia and Michael Wolf proved a very interesting result on spectral gaps: that determining the spectral gap of a material is undecidable. A problem is undecidable if it is impossible to prove one way or another. In this case, it is impossible to determine, for all materials, whether the material is gapped or gapless.
The theory behind the decidability of certain problems started in mathematics.
Mathematician Kurt Gödel proved his famous incompleteness theorems in 1931. The incompleteness theorems show that, for any set of mathematical axioms, there are some mathematical statements that can neither be proven true nor false. For example, determining whether polynomial equations with integer coefficients, known as Diophantine equations, have integer solutions is known to be undecidable. As another example, it’s impossible to determine whether a set exists with cardinality between that of the integers and that of the
real numbers. Gödel’s incompleteness theorems are a seminal result in modern mathematics, revealing that it is impossible to rely on the consistency of any formal set of axioms.
Around the same time, mathematician Alan Turing formulated what is now known as a Turing machine. A Turing machine is a theoretical computer: an abstract device that can execute algorithms by reading and writing to a memory tape.
Though a Turing machine is simple and was theorized long before modern computers, any algorithm that can be solved by any computer can essentially be solved by a Turing machine. Therefore, Turing machines are still used to this day as a mathematical model for computing.
One decision problem related to computing is known as the halting problem. The halting problem asks whether a Turing machine running any given program will stop in finite time. Turing proved that the halting problem is undecidable: It is impossible to determine, for all programs will either finish running, or they won’t.
In particular, the undecidability of the halting problem doesn’t mean that no programs can be shown to stop in finite time: Certainly any program we implement and run on a computer is an example of a program that provably halts in finite time. Rather, the undecidability of the halting problem means that there exist some programs for which the runtime can neither be shown to be neither finite nor infinite.
The halting problem is one of the most significant decision problems, with far-reaching consequences in the theory of computation.
Cubitt, Perez-Garcia and Wolf showed that the spectral gap is undecidable by proving that the spectral gap decision problem is equivalent to the halting problem.
As they described in Scientific American, and in more detail in their paper in Nature, the scientists essentially modeled material as a lattice of identical Turing machines, where the Turing machines halting implies more energy in the ground state. This formulation allows the spectral gap to be decided by the halting problem.
This proof shows that the decidability of the spectral gap depends on the amount of the material being considered. For most materials, the amount won’t affect the spectral gap. However, it is possible that in small amounts, a material may be gapless, but in larger amounts, they will have a gap.
Because the spectral gap is undecidable, it is impossible to determine what amount causes a material to become gapped. Such a material is so complex that it has yet to be constructed, but Cubitt, Perez-Garcia and Wolf’s proof shows that it is, at least theoretically, possible.
Junior Ross Dempsey, a Physics and Mathematics major, explained some of the consequences of the undecidability of the spectral gap.
“One of the famous Millennium Prize problems in mathematics is actually a physics problem: showing that Yang-Mills theories, which include the Standard Model of particle physics, have a mass gap. It’s certainly intriguing to know that the general case of this ubiquitous problem is undecidable,” Dempsey wrote in an email to The News-Letter.
He explained that undecidability is a characterization of the complexity of certain problems and is usually a result in mathematics.
“This is the first such case I know of in physics, so in that respect, it’s an interesting new result on a problem many physicists work to solve,” Dempsey said.
Indeed, though decidability is not ordinarily considered in physics, the undecidability of the spectral gap is a major result. New results on the decidability of other problems in physics may be soon to follow.