## What is a Billiard Ball Computer?

The Billiard Ball Computer Java applet 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:

- All billiard balls are centered on a grid point and move by one "square" in one time unit.
- 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.)
- The billiard balls are indistinguishable from each other.
- All collisions are elastic, in other words, no energy is lost, so the billiard ball computer can run forever.
- Mirrors can be placed in squares. They deflect balls at right angles, like this:

<- good

- 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

This web page is based on information from the book:

- Jan L.A. van de Snepscheut.
*What Computing is All About*. Springer-Verlag, 1993.

The billiard ball model of computation was first proposed in:

- Edward Fredkin and Tommaso Toffoli. Conservative Logic.
*International Journal of Theoretical Physics*, Vol. 21, pp. 219-253, 1982.

Back to the Billiard Ball Computer

Last modified on April 4, 1997 by James Lin.