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.