Partitionining cellular automata

This document has been superceded by the one here.

Basic partitioning schemes

Partitioning 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.

One of the simplest partitioning schemes is the Margolus neighbourhood, named after Norman Margolus and studied extensively in a book he co-authored, Cellular Automata Machines (CAM).

For another example of a partitioning scheme, see the Q*Bert neighbourhood.

Other partitioning schemes

There 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:

Terminology

I 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:

Block rules

[...] let us introduce a new style of cellular automaton, called a partitioning cellular automaton.

  1. The array of cells is partitioned into a collection of finite, disjoint and uniformly arranged pieces called blocks.
  2. A block rule is given that looks at the contents of a block and updates the whole block (rather than a single cell as in an ordinary cellular automaton); an example is given [...] below. The same rule is applied to every block. Note that blocks do not overlap, and no information is exchanged between adjacent blocks.
  3. The partition is changed from one step to the next, so as to have some overlap between the blocks used at one step and those used at the next one.

Models of Massive Parallelism has this to say:

A third description as block rules or partitioned cellular automata is fairly rare. It requires partitioning the cellular space into at least two (but finitely many) sets of blocks, each of finitely many types. The rule is actually specified by listing the way each block is updated. Updates with only one partition block quickly become stable or periodic, so it is necessary to provide a schedule (like even/odd times) to switch between partitions in order to allow information to spread locally from block to block [...] - p.25

...and Invertible Cellular Automata seems to agree:

At time 0 let us cut up space into finite regions, obtaining a partition, p0 of the set of sites [...]. Let us introduce a new kind of local map that takes as input the contents of a region and produces as output the new state of the whole region (rather than of a single cell). Such a map f0 allows information to be exchanged between cells of a region, but not across region boundaries. If f0 is invertible [...], the corresponding global map is invertible.
...however, then some confusion follows - it goes on to talk about lattice gasses. These are placed in a separate section - implying that they are not generally seen as being partitioning cellular automata. They observe that the updating scheme in a HPP gas is formally the same as a Margolus neighbourhood CA (making the same observation that I make here - where I say: "A similar isomorphism demonstrably exists between the Margolus neighbourhood and one of the two alternating sub-lattices generated by the 16-state rectangular scheme of Morita and Ueno.").

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.

References

  1. Margulis, Norman H., and Toffoli, Tomasso: "Cellular Automata Machines: A New Environment for Modelling", 1987;

  2. Margulis, Norman H., and Toffoli, Tomasso: "Invertible Cellular Automata", Physics D 45, 1990.

  3. Max Garzon: "Models of Massive Parallelism", 1995.

Tim Tyler | tim@tt1.org | http://cell-auto.com/