The Unsolvable Problem
Toby S. Cubitt, David Pérez-García, and Michael Wolf: Half-jokingly, one of us (Michael Wolf) asked, “Why don’t we prove the undecidability of something people really care about, like the spectral gap?” At the time, we were interested in whether certain problems in physics are “decidable” or “undecidable” — that is, can they ever be solved? We had gotten stuck trying to probe the decidability of a much more minor question, one few people care about. The “spectral gap” problem Michael was proposing that we tackle (which we will explain later) was one of central importance to physics. We did not know at the time whether this problem was or was not decidable (although we had a hunch it was not) or whether we would be able to prove it either way. But if we could, the results would be of real relevance to physics, not to mention a substantial mathematical achievement. Michael’s ambitious suggestion, tossed off almost as a jest, launched us on a grand adventure. Three years and 146 pages of mathematics later, our proof of the undecidability of the spectral gap was published in Nature.