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
The RuleSignal propagation
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:
The rule which may be thought of as being 'responsible' for the wall instability, is rule 5.