Partitionining cellular automataThis document has been superceded by the one here.
Basic partitioning schemesPartitioning is a technique which helps with designing reversible cellular automata which exhibit particular classes of behaviour. In a partitioning cellular automata, reversibility of the local map within each partition translates directly into reversibility of the whole automata.
For another example of a partitioning scheme, see the Q*Bert neighbourhood.
Other partitioning schemesThere are at least as many two dimensional partitioning models as there are ways of tesselating objects to cover planes. Not all of these exhibit desirable symmetries and regularities, though.
One way of building partitioning schems involves super-imposing two geometrically related grids, and treating these alternately.
The Margolus neighbourhood can be seen as the result of doing this with two rectangular grids. The "Q*Bert" neighbourhood is the result of doing this with two hexagonal grids. A superposition of hexagons and appropriately-sized triangles produces the Hexagonal Triangualar neighbourhood.
For many of the the same reasons that bees build hexagonal honeycombs, and partly because a hexagonal net represents the best way of packing circles in two dimensional space, hexagonal neighbourhoods are of particular interest to those modelling two-dimensional physics, or those interested in building computing structures efficiently in hardware.
There are other hexagonal partitioning neighbourhoods of some interest:
TerminologyI have stated above that "Partitioning" cellular automata are defined as being automata where local invertability is sufficient to prove global invertability.
In using this definition, I am following previous work by Morita and Ueno (e.g [here] and [here]. However, looking at the historical definitions of partitioning, it appears that a narrower concept was intended.
P.119 in Cellular Automata Machines leaves little room for doubt about what was intended:
Models of Massive Parallelism has this to say:
However they go on to conclude that: "In other words, lattice gasses and partitioning cellular automata are the same thing."
Here it appears that they have over-generalised from a single example. While there is an isomorphism between the neighbourhood used in the HPP gas and the Margolus neighbourhood, it does not follow that all lattice gas neighbourhoods have a corresponding partitioning scheme (using their definition of partitioning). Bluntly, they do not. There is no partitioning scheme corresponding to the common lattice gas neighbourhood, the "Star of David" neighbourhood. Nor is there a partitioning scheme corresponding to [Morita and Ueno's 32-state rectangular neighbourhood].
It seems to me that the term "partitioning" has been stretched beyond breaking point - and that new terminology is required. The term "partitioning" makes sense when discussing automata that can be partitioned into non-interacting regions, - but is confusing and misleading when applied to neighbourhoods which do no such thing like the Triumphant neighbourhood and the "Star of David" neighbourhood.
In my opinion, the most important "natural kind" in this area is the set of neighbourhoods where the domain and range are the same size (thus allowing an invertible automata to be constructed by forming a bijection between them).
This "umbrella" category is divided into what appears to be two main classes:
Note that I have suggested a name for the umbrella category: "Isometric neighbourhoods". This name is given because the domain and co-domain are of the same size.
Also there is a new name for the second category: "Stellated neighbourhoods".
Stellated neighbourhoods are so called because the appearance of their domain is often star-like - with pointy triangular sections poking outwards from a central region. The Star of David neighbourhood and the Distant sector neighbourhood illustrate this property best.
Automata built with "isometric neighbourhoods" may be described as "isometric cellular automata".
Invertible automata built using them may be described as "reversible isometric cellular automata", "invertible isometric cellular automata", or "finite bijective cellular automata".
Similarly, automata built using stellated neighbourhoods may be described as stellated cellular automata.
Comments about this terminology would be welcomed.