Neighbourhood

Machines which perform useful work have a long history, but their operation usually has to be guided. When guidance was eventually mechanized as well, the result was called an automaton. Irrespective of the physical form of the machine, its behavior could be summarized by calling portions of that behavior states and saying that changes in its mode of operation were accompanied by the emission and reception of signals. Altogether the result was a theory of automata, such as seen in Claude Shannon's analysis of the telephone switching system. When John von Neumann, thinking of such things as biological systems and automated factories, decided to use a mathematical model of construction and reproduction, he also decided to refer them to a two dimensional coordinate grid. Cells of the automaton were situated at integer coordinates, exchanging information with nearby cells. Thus the term cellular automaton came to mean a lattice of cells, each with a repertoire of states, uniformly connected with a neighborhood of other cells (possibly including itself), driven by signals which were simply the combined states of the cells within its neighborhood. External signals were neither received nor emitted. Dynamically, the states of the cells were updated at intervals according to a transition rule relating the new state of the cell to its old neighborhood; all updating was to be calculated simultaneously, and completed before altering any of the cells.

In summary, the four ingredients of a cellular automaton are:

• a lattice,
• some states,
• the neighborhood geometry,
• and a rule of evolution.

Each of these requirements can be examined in turn.

States

Although the states can be given names, the simplest choice is to state their number, and enumerate them. Binary automata with states (0, 1) are the simplest; Life calls them dead or inert, and live. It is possible to quibble whether a state which has never been alive should be called dead, but it is a convenient appellation. Von Neumann's automaton, had 29 states, ten of which were quiescent.

Lattice

The selection of a lattice is rarely controversial; the square Cartesian grid, of any dimension, is quite common but the low dimensions are easiest to visualize. A planar hexagonal grid is sometimes convenient; there are several three dimensional lattices, but lattice types are quite restricted in higher dimensions. There are three regular 2D lattices, one regular 3D lattice, and three regular 4D lattices. Interesting lattices in higher dimensions include the E8 lattice and Leech lattice. The latter has extraordinary symmetry but it is not known to have been used in a cellular automaton.

Normally evolution follows the Markov property, that the next configuration depends only on the present configuration; but it could reach a finite distance into the past. Edward Fredkin postulated a lattice of two time steps in order to construct reversible cellular automata, in analogy to first and second order differential equations. Diffusion equations, of first order usually not reversible, but wave equations, of second order, often are.

Rules

Transition rules admit many possibilities, usually being chosen for the intended application; certainly von Neumann carefully engineered his choices. Each of the 29 states has a useful purpose: the sixteen transmission states are used for basic signal propagation; the four confluent states have many uses; the eight sensitised states are necessary for construction, and one ground state that acts as a background. John Conway chose his Game of Life rule with equal care, seeking a well balanced evolution. Symmetry constitutes a general criterion for rule selection; simply counting the occupancy of a neighborhood's symmetry class fulfills this requirement. totalistic rules count all the cells of a given state in a neighborhood,semitotalistic rules set the reference cell apart. Golay surrounds, especially is a hexagonal lattice, make a finer distinction.

Neighbourhood

Finally, there is the matter of neighbourhoods. They could be quite capricious, but that is rarely contemplated. Giving them a radius - distance from the reference cell - is a natural choice:

• Von Neumann chose nearest neighbors with respect to Cartesian coordinates, which means i-1, i, i+1 and j-1, j, j+1 for the site (i, j). If only one index is varied at a time, the result is the von Neumann neighborhood of whose five members one is central with four ringing it.

• Varying both indices independently results in the Moore neighborhood whose nine members split into a center surrounded by a ring of eight, which in turn contains four orthogonal neighbors and four diagonal neighbors,. He explicitly mentioned that the von Neumann neighborhood could be embedded in the one he proposed. All these schemes retain the eightfold dihedral symmetry of the square lattice.

• • Even though counting neighbors seems to be a sufficient and rational decision, it was soon realized that functional analysis employs a whole series of variants of the Pythagorean theorem, the L_p spaces, defining their respective circles; the von Neumann neighbourhood could be an L₁ circle of unit radius, the Moore neighborhood an L_infinity unit circle. Larger radii create characteristic discs. L₂ is a natural reference topology, being the one which makes ordinary circles.

• • To make better sense of the use of topological discs, consider that for a von Neumann neighborhood, a cell's evolution then depends on a minimal (but symmetric) sampling of the surrounding dimensions, while the Moore neighborhood achieves a maximal sampling.

Aside from explorations resulting from tinkering with the topology used to define a neighborhood, there is a natural hierarchy of neighborhoods resulting from iterating the rule of evolution; after all, the ability to do so was a motivation for creating the concept of a cellular automaton. To ascertain the result of two generations of evolution, it is necessary to go back one step to see how the first generation could have arisen. A second generation neighborhood is therefore the union of all the neighborhoods of cells in the first generation and so on backwards for the third and further generations.

In this sense, there is a predecessor to Moore's 3x3 square, namely a 2x2 square (1x1 is considered too small to be worthy of mention as a cellular automaton). Which of the four cells is to be considered the reference cell? It need not even be near the remainder of the neighborhood; visually at least, and to make L_p radii meaningful, it is usually the cell sitting at the center of the neighborhood. To maintain the artistic integrity for square neighborhoods of even width, the lattice spacing could be doubled with cells sitting at even lattice points. Placing the evolved cells at the odd lattice points and adjusting the area allocated to depict the cell's state allows the evolution to continue while alternating parities between the sublattices.

Even width neighborhoods so constructed and utilized are called Margolus neighborhoods; Moore neighborhoods have odd widths. Two generations of a Margolus rule are equivalent to a single generation of a Moore rule; Margolus rules can even be changed on alternate generations. While this factorizes many 3x3 Moore rules, it only accounts for a small fraction of them.

Margolus neighborhoods are small enough that devising totalistic rules renders little benefit. On the other hand, Margolus was interested in reversible cellular automata, for which rules encompassing shifting, reflection, creation, annihilation, and complementation abound in such small neighborhoods; the billiard ball machine was a result.

Other arrangements

Blocking is another arrangement which Stephen Wolfram studied extensively, albeit mostly in the context of one-dimensional cellular automata. Groups of cells, say a Margolus neighborhood within a Moore neighborhood, are taken as a single entity, this increasing the number of states within an indvidual cell. The rule of evolution has to be modified accordingly, especially if the blocks overlap.

Sterechronic blocking is also permitted; Fredkin's reversible automata are the relevant example.

See also

Von Neumann neighbourhoods

Moore neighbourhoods

2x2