‘Next-Level’ Chaos Traces the True Limit of Predictability

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.”

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.

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.

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.