Isometric cellular systems

Isometric cellular systems are defined as being those where the domain and range contain the same quantity of information.

Isometric cellular systems are usually based on Isometric neighbourhoods - which are designed to facilitate their construction.

In an isometric cellular system, reversibility of the local map translates directly into reversibility of the whole system. This helps with designing reversible cellular systems which exhibit particular classes of behaviour.

Examples of isometric cellular systems

• Bijective neighbourhoods
  • Isometric neighbourhoods
    • Partitioning neighbourhoods
      • Margolus neighbourhood
      • Q*Bert neighbourhood
      • Hexagonal Triangualar

    • Stellated neighbourhoods
      • Star of David neighbourhood
      • Triumphant neighbourhood
      • The Y neighbourhood
      • Isometric von Neumann neighbourhood

  Partitioning schemes

  Partitioning cellular systems form a sub-category of isometric cellular systems. Space is divided into tesselated, non-interacting regions. Each region is then bijectively mapped onto itself. Then space is re-partitioned - and another bijective map is repeated. This process is iterated.

  P.119 in Cellular Automata Machines defines partitioning as follows:

  [...] let us introduce a new style of cellular automaton, called a partitioning cellular automaton. The array of cells is partitioned into a collection of finite, disjoint and uniformly arranged pieces called blocks. 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. 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.

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

  • Triple Hexagon neighbourhood;
  • Q*Bert neighbourhood;

  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.