|
by Charlie Wood
The future of certain theoretical systems
is unknowable,
even to an all-knowing demon.
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...
His thought experiment marked the height of
optimism about what physicists might forecast. Since then, reality
has repeatedly humbled their ambitions to understand it.
They don't have a precise position for a demon to
know.
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.
Eva Miranda, a mathematician at the Polytechnic University of Catalonia (UPC) in Spain, calls undecidability,
Pierre-Simon Laplace speculated that an all-knowing demon could perfectly predict the future of any physical system.
He was wrong. Wikimedia Commons
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,
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.
Kristina Armitage Quanta Magazine
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.
In chaotic systems, this growth can be represented as movement across a written-out number:
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:
But in doing so, he also infused it with an attribute that we might not typically associate with computers: unpredictability.
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.)
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:
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,
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.
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:
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.
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.
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.
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.
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.
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:
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,
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:
Fluids That Compute
Researchers have recently found an assortment of new limits on predictability outside quantum physics too.
Eva 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.
Eva Miranda has shown that fluids can flow in such complicated ways that trajectories through them
become undecidable.
Along with Robert Cardona, Daniel Peralta-Salas, and Francisco Presas, Miranda 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.
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.
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.
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.
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.
|
