In 1982 Edward Fredkin and Tommaso Toffoli of MIT described a computer made of nothing but hard balls bouncing around a table, guided by fixed mirrors. It was never meant to be built, but was a way to show that, in principle, a computer could work without giving off any heat.

The billiard ball computer appeared in their paper “Conservative Logic”, in the International Journal of Theoretical Physics. The authors clearly enjoyed the image, writing that the behaviour of a general-purpose computer “can be reproduced by a perfect gas placed in a suitably shaped container and given appropriate initial conditions”.

Why billiard balls

Ordinary logic gates throw information away, and in 1961 Rolf Landauer of IBM argued that erasing a bit must give off a small amount of heat. Fredkin and Toffoli had designed logic that erases nothing, and they then asked whether a real physical effect could carry it out.

Collisions between perfectly elastic balls, the same rules that describe the molecules of an ideal gas, were an obvious candidate. They lose no energy, and every collision can be run backwards in time to give back the starting positions, which is exactly the property reversible logic needs.

The rules of the game

The model uses identical hard balls moving across a square grid, each one travelling one grid space per tick along the grid lines. The balls’ size is chosen so that after a right-angle collision they stay on the grid and in step.

At each tick, a ball at a given point stands for a 1 and an empty point stands for a 0, so the pattern of balls across the grid is the computer’s data. Fixed mirrors bend a ball’s path, shift it sideways, delay it or let two paths cross safely.

A wire is simply a path a ball might take, so the shape of the mirrors is the computer’s hardware. The starting positions of the balls are its software.

The interaction gate

The basic gate is a spot where two balls, which we can call p and q, might meet. If only one arrives it carries straight on, but if both arrive they collide and each leaves along a new path at right angles to the old one.

That gives four exit paths in all. Two of them carry a ball only when both p and q arrive, so each computes AND, while the third carries one when q comes alone and the fourth when p comes alone.

Hold q at 1 by always sending in a ball, and the third path gives NOT p. With AND and NOT available, and a steady supply of extra balls, the interaction gate can build any logic circuit while the number of balls never changes.

Building the Fredkin gate

From the interaction gate the authors and their colleagues built bigger parts. A. Ressler, then a student at MIT, designed a billiard ball version of the switch gate, which sends one ball down either of two paths depending on whether a control ball is present.

The paper gives two designs for the Fredkin gate itself, one of them by Ressler and Richard Feynman. The Fredkin gate swaps two signals or leaves them alone depending on a control signal, and networks of it, fed with constants, can carry out any calculation. So in principle any computer could be drawn as a pattern of mirrors, with balls fired in at the right moments and the answer read from where they come out.

The catch

The paper was honest about the weak point, which was noise, and the authors said plainly that they would not attempt to answer the question it raised. Without some way of damping errors, they asked whether “the slightest residual noise” would be “amplified by an enormous factor during a computation”.

Charles Bennett of IBM answered it the same year, and the answer is largely yes. When round balls collide, a tiny error in position or angle roughly doubles, so a real machine would be scrambled after a few dozen collisions.

Ordinary chips avoid this trap by restoring every signal to a clean 0 or 1 at each step. That restoring costs energy, which is exactly the cost the billiard ball computer was designed to avoid.

Margolus’s digital billiards

Norman Margolus, a younger member of Fredkin’s group at MIT, found a way round the problem on paper. In “Physics-like Models of Computation”, published in Physica D in 1984, he built the billiard ball rules into a reversible cellular automaton, a grid of cells that update by fixed local rules.

In that version every ball sits in a whole cell and moves in whole steps, so there is no slow drift to amplify. One wrong cell would still go uncorrected, but the model computes without erasing anything.

Benioff’s different idea

The billiard ball computer is sometimes confused with the work of Paul Benioff of Argonne National Laboratory, but the two are different. Benioff’s 1980 paper in the Journal of Statistical Physics described a computer that runs by the rules of quantum mechanics. That was a separate and equally important idea, and QZ covers it in a profile of Paul Benioff’s atomic computer.

What the billiard balls showed

As far as anyone knows, no law of physics sets a minimum energy for computing that erases nothing. The billiard ball computer made that point with a picture anyone could follow, and it helped persuade physicists to take reversible logic seriously.

That logic turned out to be a natural fit for quantum computers, whose gates must all be reversible. Our pages on Edward Fredkin and on Fredkin and Toffoli’s reversible computing tell the rest of the story.

More like this