|
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:
The Rule1: -> 
2:  -> 
3:  -> 
4:  -> 
5:  -> 
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 IssuesThere 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:
|
Cells active: 