The X neighbourhood



Domain 1   ->   Range 1

The X neighborhood is a sister partitioning scheme to the one used in the Margolus neighbourhood. It exhibits very similar behaviour when used with appropriately translated automata. It has cells with 16 states, and uses information from neighbours in an 'X' configuration.

It is not obviously a partitioning automata in the same way as the Margolus neighbourhood, however a little thought indicates that reversibility of the local leads directly to reversibility of the global map - the defining characteristic.

When implemented in hardware, it applies the same transformation to each cell on each clock tick - and requires no apparatus to implement an alternating partitioning grid.

It also has some corresponding drawbacks, however:

  • The X neighbourhood actually generates four causally independant sub-latices. Two of these share the same cells; so if a non-uniform automata is used, they must compute esstentially the same function.
  • Cells of the domain are more widely spaced than normal. This may mean that signals have to travel further, and the automata's update frequency may suffer as a consequence;
Unfortunately, any automaton that generates so many independent sub-lattices is rather problematical from the perspective of efficient hardware implementation.

More diagrams of this neighbourhood are available here.

There are partitioning schemes from the same family available with triangular geometry.

The automata may be generalised into three dimensions. Pictures of such automata are available here.

Index | HAL | Gozilla | EoSex | Firefly | CA | Links |