Three-dimensional reversible cellular automata

The three-dimensional Billiard Ball Machine

We exhibit a reversible three dimensional partitioning cellular automata which supports universal computation and is time reversal invariant.

The model is based around the Necker neighbourhood, which is a simple three-dimensional extension of the Margolus neighbourhood.

    

Cells empty: Cells active:

The Rule

1: ->    2: ->    3: ->    4: ->    5: ->   

The model is isotropic, symmetrical under all rotations and reflections.
This means that the above rules may be applied in any orientation.
All states not explicitly mentioned remain unchanged.

A full rule table (in hexadecimal) is available here.

To illustrate how the model simulates the physics of billiard balls and mirrors in an artificial world, here are some 'ball' bounces:

    

These are sufficient to illustrate how signal propagation, signal crossing and signal delays may be implemented. Signal interaction, allowing for construction of NAND gates is allowed for by the third rule above.

Design Issues

There is more than one way of extending the billiard ball model into three dimensions, while retaining its computation universality.

A simple-minded approach would be to replace rule 5 (above) with a rule causing particles approaching one another along the longest diagonal in the cube to be dispatched along different diagonals. As there are two possible choices, this implementation would introduce a 'chirality' (handedness) into the model, which we viewed as an undesirable element. Our solution, in the form of rule five rejects this straight-forward translation and adopts an alternative method of implementing ball bounces.

Consequentially there are some qualitative differences from the standard two-dimensional billiard ball machine:

  • In three dimensions, mirrors are no longer perfectly stable and may be created or destroyed by well-timed collisions between multiple balls.
  • In two-dimensions, balls are no longer composite objects consisting of two particles, spatially separated by a single square diagonally. In three dimensions, balls are simply single active sites.
  • Curiously, in three dimensions, ball bounces occur slightly below the surface, whereas when using the X neighbourhood, ball bounces occur slightly below it.
The rule which allows mirrors to be created and destroyed is rule 5.

Tim Tyler | http://cell-auto.com/