A single ball on a fixed table can compute: Eva Miranda and Isaac Ramos prove that two-dimensional billiards are Turing complete

At the back of a bar, past the toilets, where the light gives up and the floor has acquired a colour unknown to nature, a pinball machine waits against the wall. Drop in a coin. A spring fires the ball into play, and suddenly it is ricocheting through ramps, bumpers, tunnels and targets while a carousel of lights celebrates rules nobody quite understands. Eva Miranda, Full Professor at the Universitat Politècnica de Catalunya (UPC) and affiliated researcher at the Centre de Recerca Matemàtica (CRM), invites us to look at it with a geometer’s eyes.

“A pinball machine isn’t a surface, it’s a catalogue of parts bolted together side by side,” she says. “Each bumper performs an operation. Each ramp performs another. The ball enters a part and comes out transformed. And someone, in a factory in Chicago, decided which parts to attach to which.”

That observation is the seed of a paper she has written with Isaac Ramos (ETH Zürich), Two-dimensional billiards are Turing complete. A point particle moving freely inside a bounded region of the plane and reflecting off fixed walls can simulate a universal Turing machine. One ball, walls that never move. Natural questions about where that ball goes therefore inherit the limits of computation. Two of them, reachability and periodicity, are algorithmically undecidable. There is no general algorithm that can decide these questions for every relevant initial condition: whether the trajectory will eventually reach a specified region, or whether it will be periodic.

The scarce resource

In 1990 Cristopher Moore showed that dynamical systems could carry out universal computation and inherit, with it, the undecidability of Turing’s halting problem. He proposed three-dimensional billiards as the natural setting, a particle bouncing among a forest of mirrors, and left a suspicion on record: in two dimensions, with a single ball, there might not be enough room to hide a universal machine. Later work seemed to agree. Edward Fredkin and Tommaso Toffoli had needed a crowd of balls colliding as logic gates; others needed walls in three dimensions. The most recent construction, posted in October 2025 by Rosemary Adejoh, Andreas Jakoby, Sneha Mohanty and Christian Schindelhauer, showed that a pinball machine, flippers included, can simulate a Turing machine.

The shared intuition was that dimension is the scarce resource.

A Turing machine, the model of a computer that Alan Turing wrote down in 1936, has a tape of 0s and 1s, a head that reads and writes one cell at a time, and a finite list of states with a rule saying what to do next. The universal ones can run any algorithm, and Turing proved that no procedure can decide in general whether a given machine will ever halt. A dynamical system is Turing complete when its trajectories reproduce, step by step, the evolution of a universal machine. The halting problem then travels with it.

Now, Miranda and Ramos have shown that none of the extra ingredients is necessary. For every reversible Turing machine they build a bounded planar table, smooth except at finitely many boundary points, whose billiard flow reproduces the machine’s computation exactly. Since any computation can be carried out by an equivalent reversible Turing machine, this is enough to obtain universal computation.

Each internal state becomes a short segment inside the table, each transition a corridor between two segments, and the ball’s position along a segment encodes the whole tape and the head position at once, through a ternary Cantor-set expansion. A pair of parabolic walls sharing a focus moves the head one cell. Reading and writing a symbol is harder: the wall that sorts trajectories reading a 0 from those reading a 1 is a curve with infinitely many oscillations, tilted by a minute angle wherever a symbol has to change. These tables are not polygons. Their boundaries contain structure at arbitrarily fine scales, but they are billiards in the ordinary mathematical sense. Reversibility does the rest. That every computation can be run by a reversible machine is Charles Bennett’s theorem, from 1973, and reversibility is what lets several corridors merge into one without trajectories from different transitions ever sharing a path.

Figure 1. From computation to geometry. A Turing machine’s states and transitions are encoded into the sections and corridors of a planar billiard table, where the trajectory of a single ball reproduces the computation. Image: E. Miranda and I. Ramos, PNAS, 2026.

Take away the flippers

The idea has two turns, and Miranda says both came at once. The first was the pinball paper. “That same month, someone had just proved precisely this for pinball machines. Those coincidences hurt for five minutes and then they set you free, because they force you to ask what you had that wasn’t that. And the second turn was the answer: we didn’t need the flippers.”

“The flippers are the only living part of a pinball machine. They’re the player, the external agent, the hand that decides. Well, they’re dispensable. The computation doesn’t happen at the paddles, it happens in the shape of the boundary.”

Take away the player, the moving parts, the third dimension, and what survives is still universal. What remains is a billiard, the object Moore had asked about in the first place, and his obstruction dissolves once you notice that the wrong thing was being counted. For Miranda, that was the shift in perspective: Moore had been counting dimensions, when the real resource was the geometry of the boundary.

For a reader meeting the idea for the first time, she offers a picture. “A billiard table that computes doesn’t look like a computer. It looks like a badly drawn labyrinth, full of corners and arcs that seem like whims. The program is the shape of the walls. The algorithm is, literally, the trajectory. And there’s only one ball. I know, not very exciting if you’re thinking of fifteen balls and a cue ball.”

Eva Miranda at UCLA.

A barrier of precision and a barrier of logic

Billiards have been the standard laboratory for chaos since Yakov Sinai’s dispersing tables in the 1960s; a computing table adds a second kind of barrier. “Chaos imposes a barrier of precision; undecidability imposes a logical barrier,” Miranda says. “Laplace, in 1814, sold us a demon: an intelligence that knew every position and every velocity in the universe, for which the future would be as present as the past. Poincaré, after a famous error in a prize-winning memoir, sent it the first invoice. The demon can predict, but it is insatiable. To see a little further it needs ever more digits, and the cost grows exponentially. That’s chaos.”

Undecidability leaves no such bargain. “Even if we know the equations and the initial data exactly, there may be no algorithm that decides whether a trajectory will ever enter a given region. That doesn’t mean every individual trajectory is mysterious. In many concrete cases we’ll get an answer. What’s impossible is a universal method that settles every case.”

In the tables of the paper the distinction takes a geometric form. If the machine halts, the ball reaches the halting segment perpendicular to the wall, reverses, retraces its own path and closes into a periodic orbit. If the machine never halts, the orbit never closes. Whether a trajectory is periodic becomes exactly as hard as whether a program halts. “Hilbert posed the Entscheidungsproblem in 1928. In 1936 Turing answered it with a resounding no. What we’ve done is carry that ‘no’ from logic onto a billiard table.” Laplace’s demon, she adds, is not defeated by lack of precision. “In some cases, the procedure it would need simply doesn’t exist.”

The minimal mechanism

The billiard sits at the end of a line of work that has occupied Miranda for most of a decade. “The underlying question has always been the same: what is the minimal geometric mechanism that allows a physical system to do universal computation, and how can we detect it?”

The starting point was fluids, motivated in part by Terence Tao’s programme relating the computational capacity of a fluid to the formation of singularities in finite time, and hence to the regularity problem for Navier-Stokes. In 2021, with Robert Cardona, Daniel Peralta-Salas and Francisco Presas, she carried the problem into contact geometry and constructed Turing complete Euler flows; cosymplectic geometry later gave Turing complete stationary solutions of Navier-Stokes, with Søren Dyhr, Ángel González-Prieto and Peralta-Salas. “Each step opened the same question: which part of the previous structure was really necessary? Could we abandon the fluid equations? Reduce the dimension? Do without a potential or an external mechanism?”

The tool that turned a string of examples into a method is Topological Kleene Field Theory, or TKFT, developed with González-Prieto and Peralta-Salas. It brings under one roof two theories that had never previously been connected in this way: Kleene’s construction of computable functions and the topological field theories of Atiyah and Segal, where pieces of space are glued along their boundaries and the gluing becomes composition of maps. Compositions, in other words, can be drawn.

Topological Kleene Field Theory: pieces of space glued along their boundaries compose like functions. Image: E. Miranda, after a figure in the TKFT paper (arXiv:2503.16100)

Which is where the machine at the back of the bar comes back in. “A pinball is a decomposition into bordisms drawn by someone who had never heard the word bordism. Once I saw it that way, the question became irresistible: what if a billiard was already enough?”

“The billiard is the most demanding test of that process of simplification. A single particle. The whole program is inscribed in the geometry of the boundary.”

“What we’ve kept finding is that the frontier of undecidability lies much closer to the elementary models of classical mechanics than we would have imagined.”

How many planets does it take to compute?

The paper’s last section moves from the table to the sky. “Billiards aren’t an isolated toy. We could say they’re a kind of skeleton of classical mechanics.” A gas of hard spheres can be reformulated exactly as a billiard flow in configuration space, and in celestial mechanics, where there are no rigid walls, near-collisions between bodies can play their part: long Keplerian arcs separated by brief encounters which, in the limit, resemble reflections. “Between two collisions, gravity transports the information; at each encounter, it transforms it.”

“The connection suggests an almost provocative question: how many planets does it take for gravity to compute? Two bodies give us Kepler’s orderly world. With three, the chaotic mechanisms discovered by Poincaré already appear. But there could be yet another threshold: the minimum number of bodies needed for Newtonian dynamics to simulate any Turing machine. We can call that number the Turing scale of the n-body problem. How many does it take for undecidability to appear? Maybe three, maybe five, maybe many more. It’s a completely open question.”

Counting the Sun and eight planets, the solar system has nine principal bodies, and Miranda is careful to say that a Turing scale of nine or less would not make it a computer: the masses and the initial configuration would have to be very specific as well. “But it would show that a system with a number of planets comparable to ours could, in principle, contain a universal computation.” The decisive step, proving that gravitational orbits follow a computation for arbitrarily long times and not just over a finite interval, is still missing. “We’re not claiming that the future of the Earth or of Mercury is mathematically undecidable. We’re asking whether a finite planetary architecture exists that can hide Turing’s halting problem inside gravitational motion and the final push. And then comes the real challenge: can we reduce the number of bodies to just three bodies? If so, we would be confronting one of the problems that already resisted Newton: the three-body problem, long known to be non-integrable and capable of highly chaotic behaviour. That would reveal a genuinely new facet of the three-body problem: not just unpredictability through chaos, but algorithmic undecidability.”

A question at the end of a talk

Miranda met Isaac Ramos in Madrid, at a colloquium she gave there. “He came up to ask questions at the end, the kind that make you see straight away that somebody hasn’t come just to listen.” They coincided again at UCLA, with Terence Tao, and she then supervised his undergraduate thesis, together with González-Prieto and Peralta-Salas, on plugs, a topic that appears to have nothing to do with billiards. “I say appears because plugs are precisely the piece that lets you modify a vector field inside a small region without touching anything outside: the way of doing surgery on a dynamics. In billiards we do something not so different, building zones where the trajectory is forced to execute a specific instruction.”

Isaac Ramos and Eva Miranda.

They met again at ETH Zürich in the autumn of 2025, while Miranda was teaching her Nachdiplom course Singular Symplectic Manifolds at the Forschungsinstitut für Mathematik. Ramos asked her for a topic for his master’s paper and she proposed billiards: study the undecidability of pinball and connect it with billiard dynamics. “It was a bold assignment for a master’s project, because there was no guarantee it would work, but he went in fully, and that’s where it all began.” The same semester brought Stephen Wolfram’s visit to Zürich, credited in the paper’s acknowledgements as the source of several of the questions behind it, and covered by the CRM in a previous article.

She tells the story at length because she thinks it is useful to anyone weighing up a doctorate.

“It’s worth asking the question at the end of the talk. Almost every collaboration I have started that way, not with a call for proposals or a strategic plan.”

“A topic shouldn’t be chosen for its immediate return but for the machinery it teaches you to use. And the problems worth doing are precisely the ones you don’t know whether they can be solved. I proposed an open problem to Isaac, not an exercise, and he accepted the risk. That’s how we work in our group, and anyone who wants to come and do a thesis with us will find questions of that kind, at the frontier between geometry, dynamics and computability, without a net and with a lot left to discover.”

The paper closes on a question it does not answer: whether these barriers survive quantisation. “When we turn the ball into a wave, does the machine stop computing? The honest answer is that we don’t know yet. My hypothesis is that undecidability doesn’t disappear, it changes place. In the classical system it’s written in the trajectories; in the quantum one it could reappear in the spectrum, in the eigenfunctions or, in open systems, in the resonances.”

Nothing transfers automatically: a quantised billiard follows a wave function rather than a point, and detail smaller than the wavelength can become invisible. The image Miranda keeps returning to is that of quantum scars. Eric Heller observed in 1984 that some eigenfunctions of a chaotic billiard pile up probability along an unstable periodic orbit. “The wave doesn’t completely forget the classical dynamics. It keeps an imprint of the path the ball would run over and over again.” For the computational trajectories in their construction, halting corresponds exactly to periodicity, which makes the connection tempting. It is not a theorem. With Leonid Polterovich she is trying to design a semiclassical machine, and finds the opposite outcome just as interesting: that quantisation erases undecidability at each fixed quantum scale, and it reappears only in the classical limit. Some quantum systems would then be more predictable than the classical dynamics behind them.

“The question is whether the classical machine casts a quantum shadow, or whether quantisation acts as a filter capable of erasing the undecidable.”