In math and computer science, researchers have long understood that some questions are fundamentally unanswerable. Now physicists are exploring how even ordinary physical systems put hard limits on what we can predict, even in principle.
Illustration of a blindfolded demon attempting to sense the contents of a cosmic crystal ball.
The future of certain theoretical systems is unknowable, even to an all-knowing demon.
The French scholar Pierre-Simon Laplace crisply articulated his expectation that the universe was fully knowable in 1814, asserting that a sufficiently clever “demon” could predict the entire future given a complete knowledge of the present. His thought experiment marked the height of optimism about what physicists might forecast. Since then, reality has repeatedly humbled their ambitions to understand it.
One blow came in the early 1900s with the discovery of quantum mechanics. Whenever quantum particles are not being measured, they inhabit a fundamentally fuzzy realm of possibilities. They don’t have a precise position for a demon to know.
Another came later that century, when physicists realized how much “chaotic” systems amplified any uncertainties. A demon might be able to predict the weather in 50 years, but only with an infinite knowledge of the present all the way down to every beat of every butterfly’s wing.
In recent years, a third limitation has been percolating through physics — in some ways the most dramatic yet. Physicists have found it in collections of quantum particles, along with classical systems like swirling ocean currents. Known as undecidability, it goes beyond chaos. Even a demon with perfect knowledge of a system’s state would be unable to fully grasp its future.
“I give you God’s view,” said Toby Cubitt, a physicist turned computer scientist at University College London and part of the vanguard of the current charge into the unknowable, and “you still can’t predict what it’s going to do.”
Eva Miranda, a mathematician at the Polytechnic University of Catalonia (UPC) in Spain, calls undecidability a “next-level chaotic thing.”
A man wearing a wig stands in front of a chalkboard.
Pierre-Simon Laplace speculated that an all-knowing demon could perfectly predict the future of any physical system. He was wrong.
Undecidability means that certain questions simply cannot be answered. It’s an unfamiliar message for physicists, but it’s one that mathematicians and computer scientists know well. More than a century ago, they rigorously established that there are mathematical questions that can never be answered, true statements that can never be proved. Now physicists are connecting those unknowable mathematical systems with an increasing number of physical ones and thereby beginning to map out the hard boundary of knowability in their field as well.
These examples “place major limitations on what we humans can come up with,” said David Wolpert, a researcher at the Santa Fe Institute who studies the limits of knowledge but was not involved in the recent work. “And they are inviolable.”
The Blackest of Boxes
A striking example of unknowability came to physics in 1990 when Cris Moore, then a graduate student at Cornell University, designed an undecidable machine with a single moving part.
His setup — which was purely theoretical — resembled a highly customizable pinball machine. Imagine a box, open at the bottom. A player would fill the box with bumpers, move the launcher to any position along the bottom of the box, and fire a pinball into the interior. The contraption was relatively simple. But as the ball ricocheted around, it was secretly performing a computation.
Moore had become fascinated with computation after reading Gödel, Escher, Bach, a Pulitzer Prize–winning book about systems that reference themselves. The system that most captured his imagination was an imaginary device that had launched the field of computer science, the Turing machine.
Defined by the mathematician Alan Turing in a landmark 1936 paper, the Turing machine consisted of a head that could move up and down an infinitely long tape, reading and writing 0s and 1s in a series of steps according to a handful of simple rules telling it what to do. One Turing machine, following one set of rules, might read two numbers and print their product. Another, following a different set of rules, might read one number and print its square root. In this way, a Turing machine could be designed to execute any sequence of mathematical and logical operations. Today we would say that a Turing machine executes an “algorithm,” and many (but not all) physicists consider Turing machines to define the limits of calculation itself, whether performed by computer, human or demon.
Moore recognized the seeds of Turing machine behavior in the subject of his graduate studies: chaos. In a chaotic system, no detail is small enough to ignore. Adjusting the position of a butterfly in Brazil by a millimeter, in one infamous metaphor, could mean the difference between a typhoon striking Tokyo and a tornado tearing through Tennessee. Uncertainty that starts off as a rounding error eventually grows so large that it engulfs the entire calculation. In chaotic systems, this growth can be represented as movement across a written-out number: Ignorance in the one-tenths place spreads left, eventually moving across the decimal point to become ignorance in the tens place.
Moore designed his pinball machine to complete the analogy to the Turing machine. The starting position of the pinball represents the data on the tape being fed into the Turing machine. Crucially (and unrealistically), the player must be able to adjust the ball’s starting location with infinite precision, meaning that specifying the ball’s location requires a number with an endless procession of numerals after the decimal point. Only in such a number could Moore encode the data of an infinitely long Turing tape.
Then the arrangement of bumpers steers the ball to new positions in a way that corresponds to reading and writing on some Turing machine’s tape. Certain curved bumpers shift the tape one way, making the data stored in distant decimal places more significant in a way reminiscent of chaotic systems, while oppositely curved bumpers do the reverse. The ball’s exit from the bottom of the box marks the end of the computation, with the final location as the result.
Moore equipped his pinball machine setup with the flexibility of a computer — one arrangement of bumpers might calculate the first thousand digits of pi, and another might compute the best next move in a game of chess. But in doing so, he also infused it with an attribute that we might not typically associate with computers: unpredictability.
A young man wears a jacket and tie
In a landmark work in 1936, Alan Turing defined the boundary of computation by describing the key features of a universal computing device, now known as a Turing machine.
Some algorithms stop, outputting a result. But others run forever. (Consider a program tasked with printing the final digit of pi.) Is there a procedure, Turing asked, that can examine any program and determine whether it will stop? This question became known as the halting problem.
Turing showed that no such procedure exists by considering what it would mean if it did. If one machine could predict the behavior of another, you could easily modify the first machine — the one that predicts behavior — to run forever when the other machine halts. And vice versa: It halts when the other machine runs forever. Then — and here’s the mind-bending part — Turing imagined feeding a description of this tweaked prediction machine into itself. If the machine stops, it also runs forever. And if it runs forever, it also stops. Since neither option could be, Turing concluded, the prediction machine itself must not exist.
(His finding was intimately related to a groundbreaking result from 1931, when the logician Kurt Gödel developed a similar way of feeding a self-referential paradox into a rigorous mathematical framework. Gödel proved that mathematical statements exist whose truth cannot be established.)
In short, Turing proved that solving the halting problem was impossible. The only general way to know if an algorithm stops is to run it for as long as you can. If it stops, you have your answer. But if it doesn’t, you’ll never know whether it truly runs forever, or whether it would have stopped if you’d just waited a bit longer.
“We know that there are these kinds of initial states that we cannot predict ahead of time what it’s going to do,” Wolpert said.
Since Moore had designed his box to mimic any Turing machine, it too could behave in unpredictable ways. The exit of the ball marks the end of a calculation, so the question of whether any particular arrangement of bumpers will trap the ball or steer it to the exit must also be undecidable. “Really, any question about the long-term dynamics of these more elaborate maps is undecidable,” Moore said.
A man stands in a library.
Cris Moore developed one of the earliest and simplest undecidable physical systems.
Moore’s pinball machine went beyond ordinary chaos. A tornado forecaster can’t say exactly where a tornado will touch down for two reasons: the forecaster’s ignorance of the precise position of every Brazilian butterfly, and limited computing power. But Moore’s pinball machine featured a more fundamental form of unpredictability. Even for someone with complete knowledge of the machine and unlimited computing power, certain questions regarding its fate remain unanswerable.
“This is a bit more dramatic,” said David Pérez-García, a mathematician at the Complutense University of Madrid. “Even with infinite resources, you cannot even write the program that solves the problem.”
Other researchers have previously come up with systems that act like Turing machines — notably checkerboard grids with squares flickering on and off depending on the colors of their neighbors. But these systems were abstract and intricate. Moore crafted a Turing machine out of a simple apparatus you could imagine sitting in a lab. It was a vivid demonstration that a system obeying nothing more than high school physics could have an unpredictable nature.
“It’s a bit shocking that it’s undecidable,” said Cubitt, who lectured about Moore’s machine after it captured his imagination as a graduate student. “It’s literally a single particle bouncing around a box.”
After getting his doctorate in physics, Cubitt shifted into mathematics and computer science. But he never forgot the pinball machine, and how computer science put limits on the machine’s physics. He wondered whether undecidability touched any physics problems that really matter. Over the last decade, he has discovered that it does.
Modern Mystery Materials
Cubitt put undecidability on a collision course with large quantum systems in 2012.
He, Pérez-García and their colleague Michael Wolf had gotten together for coffee during a conference in the Austrian Alps to debate whether a niche problem might be undecidable. When Wolf suggested they put that problem aside and instead tackle the decidability of one of the biggest problems in quantum physics, not even he suspected they might actually succeed.
“It started as a joke. Then we started to cook up ideas,” Pérez-García said.
Wolf proposed targeting a defining property of every quantum system called the spectral gap, which refers to how much energy it takes to jostle a system out of its lowest energy state. If it takes some oomph to do this, a system is “gapped.” If it can become excited at any moment, without any infusion of energy, it is “gapless.” The spectral gap determines the color that shines from a neon sign, what a material will do when you remove all heat from it, and — in a different context — what the mass of the proton should be. In many cases, physicists can calculate the spectral gap for a specific atom or material. In many other cases, they can’t. A million-dollar prize awaits anyone who can rigorously prove from first principles that the proton should have a positive mass.
Top: A mean wearing a blue blazer stands on a city street. Bottom: A man with a half-smile wears a t-shirt.(left): A mean wearing a blue blazer stands on a city street. Right: A man with a half-smile wears a t-shirt.
David Pérez-García (top) and Toby Cubitt designed a quantum material whose state can capture any calculation possible for a Turing machine.
David Pérez-García (left) and Toby Cubitt designed a quantum material whose state can capture any calculation possible for a Turing machine.
Cubitt, Wolf and Pérez-García aimed high. They sought to prove or disprove the existence of a single strategy — a universal algorithm — that would tell you whether anything from a proton to a sheet of aluminum had a spectral gap or not. To do so, they resorted to the same approach Moore had used with his pinball machine: They devised a fictitious quantum material that could be set up to act like any Turing machine. They hoped to rewrite the spectral gap problem as the halting problem in disguise.
Over the next three years they churned out 144 pages of dense mathematics, combining a handful of major results from the previous half-century of math and physics. The extremely rough idea was to use the quantum particles in a flat material — a grid of atoms, basically — as a stand-in for the Turing machine’s tape.
Because this was a quantum material, the particles could exist in a superposition of multiple states at the same time — a quantum combination of different possible configurations of the material. The researchers used this feature to capture the different steps of the calculation. They set up the superposition so that one of these possible configurations represented the initial state of the Turing machine, another configuration represented the first step of the calculation, another represented the second step, and so on.
Finally, using techniques from quantum computing, they fiddled with the interactions between the particles so that if the superposition represented a calculation that halted, the material would have an energy gap. And if the computation continued forever, the material had no gap. In a paper published in Nature in 2015, they proved that the spectral gap problem is equivalent to the halting problem — and therefore undecidable. If someone handed you some complete description of the material’s particles, it would either have a gap or not. But calculating this property mathematically, from the way the particles interact, couldn’t be done, even if you had a quantum supercomputer from the year 3000.
In 2020, Pérez-García, Cubitt and other collaborators repeated the proof for a chain of particles (as opposed to a grid). And last year, Cubitt, James Purcell and Zhi Li further extended the setup to devise a material that, when subjected to a magnetic field that grows increasingly intense, will transition from one phase of matter to another at an unpredictable moment.
Their research program inspired other groups. In 2021, Naoto Shiraishi, then at Gakushuin University in Japan, and Keiji Matsumoto of Japan’s National Institute of Informatics dreamt up a similarly bizarre material, in which it was impossible to predict whether energy would “thermalize,” or spread evenly throughout the substance.
None of these results mean that we can’t predict specific properties of specific materials. Theorists might be able to calculate, for example, copper’s energy gap, or even whether all metals thermalize under certain conditions. But the research does prove that no master method works for all materials.
Said Shiraishi: “If you think too generally, you will fail.”
Fluids That Compute
Researchers have recently found an assortment of new limits on predictability outside quantum physics too.
Miranda of UPC has spent the last few years trying to work out whether liquids can act as computers. In 2014, the mathematician Terence Tao pointed out that if they could, perhaps a fluid could be programmed to slosh in just the right way to bring forth a tsunami of unlimited violence. Such a tsunami would be unphysical, since no wave can accommodate infinite energy in the real world. And so anyone who found such an algorithm would prove that the theory of fluids, called the Navier-Stokes equations, predicts impossibilities — another million-dollar problem.
A woman with curly hair poses by the beach.
Eva Miranda has shown that fluids can flow in such complicated ways that trajectories through them become undecidable.
Miranda and colleagues started with a fluid obeying simpler equations. They converted a Turing machine’s tape into a location on a plane (akin to the bottom of Moore’s pinball box). As the Turing machine ticks along, this point on the plane jumps around. Then, with a series of geometric transformations, they were able to turn the hopping of this point into the smooth current of a fluid flowing through 3D space (albeit a weird one curled into a doughnut in its center). To illustrate the idea over Zoom, Miranda pulled out a rubber duck from behind her computer.
“While the trajectory of the point in the water — it could be a duck — is moving around, this is the same as the tape of your Turing machine advancing somehow,” she said.
And with Turing machines comes undecidability. In this case, a calculation that halts corresponds to a current that carries a duck to some specific region, while a never-ending calculation corresponds to a duck that forever avoids that spot. So deciding a duck’s ultimate fate, the group showed in a 2021 publication, was impossible.
Computing in Reality
While these systems have physically implausible features that would stop an experimentalist from building them, even as blueprints they show that computers and their undecidable problems are deeply woven into the fabric of physics.
“We live in a universe where you can build computers,” Moore told me over Zoom on a sunny December afternoon from his backyard garden in Santa Fe. “Computation is everywhere.”
Even if someone attempted to build one of the machines depicted in these blueprints, however, researchers point out that undecidability is a feature of physical theories and cannot literally exist in real experiments. Only idealized systems that involve infinity — an infinitely long tape, an infinitely extensive grid of particles, an infinitely divisible space for placing pinballs and rubber ducks — can be truly undecidable. No one knows whether reality contains these sorts of infinities, but experiments definitely don’t. Every object on a lab bench has a finite number of molecules, and every measured location has a final decimal place. We can, in principle, completely understand these finite systems by systematically listing every possible configuration of their parts. So because humans can’t interact with the infinite, some researchers consider undecidability to be of limited practical significance.
“There is no such thing as perfect knowledge, because you cannot touch it,” said Karl Svozil, a retired physicist associated with the Vienna University of Technology in Austria.
“These are very important results. They are very, very profound,” Wolpert said. “But they also ultimately have no implications for humans.”
Other physicists, however, emphasize that infinite theories are a close — and essential — approximation of the real world. Climate scientists and meteorologists run computer simulations that treat the ocean as if it were a continuous fluid, because no one can analyze the ocean molecule by molecule. They need the infinite to help make sense of the finite. In that sense, some researchers consider infinity — and undecidability — to be an unavoidable aspect of our reality.
“It’s sort of solipsistic to say: ‘There are no infinite problems because ultimately life is finite,’” Moore said.
And so physicists must accept a new obstacle in their quest to acquire the foresight of Laplace’s demon. They could conceivably work out all the laws that describe the universe, just as they have worked out all the laws that describe pinball machines, quantum materials, and the trajectories of rubber ducks. But they’re learning that those laws aren’t guaranteed to provide shortcuts that allow theorists to fast-forward a system’s behavior and foresee all aspects of its fate. The universe knows what to do and will continue to evolve with time, but its behavior appears to be rich enough that certain aspects of its future may remain forever hidden to the theorists who ponder it. They will have to be satisfied with being able to discover where those impenetrable pockets lie.
“You’re trying to discover something about the way the universe or mathematics works,” Cubitt said. “The fact that it’s unsolvable, and you can prove that, is an answer.”