a technique known as partitioning
which allows reversible cellular automata to be relatively simply constructed.
In a partitioning automata,
reversibility of the global map is equivalent to reversibility of a particular
local map. As local reversibility may be much more easily tested for,
this method facilitates the construction of reversible automata.
There are a large number of possible ways of partitioning cellular
automata into finite groups of whole cells. Typically different schemes can be
used to generate automata with different dimensions, connectivity and
- Two dimensions
- Square automata
- The Margolus neighbourhood
- The X neighbourhood
- Each site is divided into four parts. The next state at each locus
is determined by the present state of the lower left part of the site
to the upper right, the upper right part of the site to the lower
left, the upper left part of the site to the lower right, and the
lower right part of the site to the upper left cell. The
diagrams on the relevant page should
help to make this clear.
The plane is divided into two independent sub-lattices by this
Unlike the Margolus neighbourhood
there is no clear partitioning scheme - however bijectivity (reversibility)
of the local map is clearly equivalent to that of the global one -
the defining characteristic of a partitioning automata.
- Three dimensions
- Cuboid automata
- The Necker neighbourhood
- This is a simple extension of the Margolus neighbourhood to three
- The 3D X neighbourhood
- This is a generalisation of the two-dimensional version.
Each site is divided into eight parts, which may be visualised as being
arranged is a 2×2×2 stack of cubes. The next state at each
locus is determined by the eight corresponding loci in the neighbours
which touch the site only by their corners. Again,
a diagram makes this clear.
The plane is again divided into two independent sub-lattices by this