What is a Billiard Ball Computer?

The Billiard Ball Computer simulator presents the billiard ball model of computation, first proposed by Edward Fredkin and Tommaso Toffoli.

Using a two-dimensional grid, billiard balls, and mirrors, you can model a simple computation, such as a switch. There are a couple of rules:

1. All billiard balls are centered on a grid point and move by one "square" in one time unit.
2. The above rule can be followed only if balls collide with each other at right angles. No head-on collisions are allowed. (If you try to set up a head on collision in the applet, the balls go through each other.)
3. The billiard balls are indistinguishable from each other.
4. All collisions are elastic, in other words, no energy is lost, so the billiard ball computer can run forever.
5. Mirrors can be placed in squares. They deflect balls at right angles, like this:
   
   ← good
   
   
6. A ball can't bounce of an "edge" of a mirror, like this:
   
   ← bad
   
   (If you try set this up in the applet, the ball will go through the mirror.)

So how does this model computation? Let's look at an example, a simple device that, given two boolean variables a and b, returns which of the following boolean expression holds: a and b, a and not b, or b and not a. This device requires no mirrors, only billiard balls:

In four time units, any balls that were located at points a and b will be at one of the four output points. We can think of the presence or the absence of a ball at a to mean a is true or false, respectively. This applies to any labeled point. Notice that if there is a ball at a and a ball at b (a = true and b = true), then there will be a ball at a and b and one at b and a. Likewise, if there is a ball at a but not at b (a = true and b = false), then there will be a ball at a and not b.

Let's look at a slightly more complex device, one that uses mirrors:

This acts as a simple switch. Notice that the ball that leaves at the output labeled a may be the ball that entered at the input a, or it may be the ball that entered at the input x, but since the balls are indistinguishable, it doesn't matter.

Since billiard balls are indistinguishable, it is possible to create an "interference-free" crossing, where two balls cross paths, using only mirrors.

For more information

• Billiard-ball computer in Wikipedia
• Edward Fredkin and Tommaso Toffoli. Conservative Logic. International Journal of Theoretical Physics, Vol. 21, pp. 219–253, 1982. The first description of a billiard-ball computer.
• Jan L.A. van de Snepscheut. What Computing is All About. Springer-Verlag, 1993.

---

Back to the Billiard Ball Computer

Last modified on November 29, 2015 by James Lin.