Next: The vocabulary of Up: History Previous: The Wolfram era

# One dimensional automata

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.

Next: The vocabulary of Up: History Previous: The Wolfram era

Harold V. McIntosh
E-mail:mcintosh@servidor.unam.mx