|
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). The X neighborhood is a sister partitioning scheme to the one used in the Margolus 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 is one common hexagonal partitioning scheme used by lattice gas enthusiasts which divides each hexagon into six triangles. This is known as the "Star of David" neighbourhood. We have a page devoted to this neighbourhood. There is another partitioning hexagonal neighbourhood of significant interest. This is the "Q*Bert" neighbourhood. We have a page devoted to this neighbourhood.
|