Two-dimensional reversible cellular automata

Two-dimensional Billiard Ball Machine (X neighbourhood)

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

The model used is based on Norman Margolus's implementation of a two-dimensional cellular automata based on Edward Fredkin's billiard-ball model.

Our model is based around the X neighbourhood, which shares many features with the Margolus neighbourhood.

The X neighbourhood

Domain:    Range:   

The Rule

Signal propagation
        
Signal interaction
  
Unchanged
                            

To illustrate how the model simulates the physics of billiard balls and mirrors in an artificial world, here is a ball bounce:
    

These are sufficient to illustrate how signal propagation, signal crossing, signal interaction and signal delays may be implemented.

Although balls take up essentially the same quantity of space, the model uses twice as many bits to create each wall element as the original Margoulis neighbourhood model - a typical circuit takes up significantly more space as an immediate consequence of this.

When comparing with the two dimensional billiard-ball model there are some clear differences as well as the clear similarities:

  • Curiously, in three dimensions, ball bounces occur slightly below the surface, whereas when using the X neighbourhood, ball bounces occur slightly below it.
  • 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 compound objects chich may be split by misplaced mirrors. In three dimensions, balls are single sites.

The rule which may be thought of as being 'responsible' for the wall instability, is rule 5.

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