Three dimensional reversible cellular automata

The three-dimensional Billiard Ball Machine (X neighbourhood)

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

The model used is derived from Norman Margolus's implementation of a two-dimensional cellular automata based on Edward Fredkin's billiard-ball model - which was developed in the process of studying the ultimate physics of computation.

The model is based around the 3D X neighbourhood, which is a simple three-dimensional extension of the X neighbourhood.

Cells empty

Cells active

Cells empty     Cells active

Domain

Range

Domain   ->   Range

Domain

Range

  ->  

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" (i.e. the domain is "shrunk" down to form the range).


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