To make a one dimensional automaton, a series of cells is strung out
along a line, the simplest assumption being that all the cells have the
same number of similar states, and that the rules of evolution will be
the same for all of them. The idea of forming the cells into a line
implies a linear order, but of course other arrangements are possible,
both in terms of the dimension and the connectivity of the cells. This
is the second element of definition for a cellular automaton -- the
relationship between the cells, or the kinds of neighborhoods which
they form. Again, the simplest neighborhood would consist of a cell and
its nearest two neighbors; generally speaking we would take a
neighbborhood to consist of **r** neighbors on each side, giving **2r+1**
for the total number of cells in a neighborhood.

There are some small quibbles to be made. If a chain is finite, it has ends, which surely do not have the same neighborhoods as the interior cells. Either they can be treated differently, or the chain can be imagined to close into a ring, which would preserve the uniformity of all the neighborhoods. Also, it is considered preferable to work with symmetric neighborhoods, each one centered on its own cell, rather than worrying about irregular neighborhoods. An interesting exception would be to work exclusively with a single neighbor, always on the same side, but that is another story.

Thus there arises Wolfram's notation for a linear cellular
automaton which has **k** states within each cell, and such that it,
together with **r** cells on either side, is considered to form a
neighborhood. In reality, a neighborhood does not have to be centered
on its cell; for example when its length is an even number of cells,
succeeding generations might be staggered by half a cell, and the
radius assumed to be half-integral.

There is one final ingredient in the definition of a cellular automaton, which is the rule of transition by which the cell changes state from one generation to the next, conventionally assumed to be the same rule for each neighborhood. It is the judicious selection of a rule as much as anything that makes a particular automaton interesting or not.

Conway's game of * Life*
was the result of a particular choice of rule for
a two dimensional binary automaton -- two states per cell -- whose
neighborhoods contained the cell in the center and the eight cells
touching it, four of them laterally and four of them diagonally. The
announced criteria by which that particular rule was chosen were that a
field of cells should neither dwindle away to nothing -- all zeroes
-- or eventually fill up completely -- all ones. Reportedly, he examined
many different rules before choosing the particular one which gave us
his famous game; even so, so much variety was encountered with that one
particular rule that years passed before many others were studied.

Wolfram's further work, mostly done at the Institute for Advanced Studies in Princeton, systematically examined all the possible rules for one dimensional automata. His recent book [121], a collection of reprints comprising much of his work on automata, contains an extensive appendix tabulating diverse properties of all 256 automata.

In two dimensions there are far too many possibilities -- vastly more so
even than in one dimension -- for there to be a chance to try
everything, even with a very fast computer. Notwithstanding, Dewdney's
column in a recent issue of Scientific American describes a three
dimensional variant of * Life*
devised by Carter Bays [6,7,8].
With twenty seven cells per neighborhood, its analysis has to be far
beyond the reach of either present methods or present and foreseeable
computers. However, it is not necessary to choose such an ambitious
model to gain useful insight and obtain interesting results. So, even
the one dimensional automata of type constitute a reasonable
starting point for systematic studies.

E-mail:mcintosh@servidor.unam.mx