Next: Probability theory Up: History Previous: One dimensional automata

# The vocabulary of automata theory

One of the heritages of the interest in Life is a rich vocabulary of such picturesque terms as still lifes, gliders and so on, describing typical artifacts encountered during evolution; even though of two-dimensional origin, they are freely used for other automata.

Similarly, Wolfram has created some basic descriptive terms by which automata can be classified according to their rules of evolution, not to mention their classification into four phenomenological evolutionary types.

For automata, a neighborhood contains three cells, each of which exists in one of two states; altogether eight possible neighborhoods. Since there is nothing to require evolution of a given neighborhood to lead to one value of the new cell or another, there are 256 possible ways that each set of eight different neighborhoods can evolve into the next generation, starting with the possibility that everything evolves into zero and ending with the possibility that everything evolves into one.

The choice of the words ``zero'' and ``one'' assumes a decision to number the states of an automaton, which is certainly convenient for computer processing, or even a plain mathematical discussion. Yet the choice is quite arbitrary; Conway must have thought that the more vivid dichotomy between ``live'' and ``dead'' or ``inactive'' would make his game more appealing. Naturally the states of an automaton displayed upon a color television screen would be the colors of the pixels themselves.

As suggested by the choice of a numerical representation, the easiest way to enumerate neighborhoods is to make up a binary number whose eight digits tell how the neighborhoods 000, 001, 010, and so on evolve. Every evolutionary rule gets its own serial number in the process; it is convenient to always do this in a standard way and refer to the rule by the decimal equivalent of the resulting number. We might call the following choice its Wolfram rule number: Set out the possible sequences of cells in reverse lexicographic order:

The second row shows how the three-cell neighborhoods evolve for Wolfram's Rule 22, the decimal equivalent of the eight-digit binary number 00010110. This ordering of neighborhoods is natural if one thinks in terms of ``high order first'' but is just the opposite of the one used in Perry's article [95].

The working of the rule of evolution can be seen in the following sample of ten generations of evolution of Rule 22 from a randomly chosen initial configuration. A cyclic ring is assumed, so the first cell in each row is the right neighbor of the last cell, just as the last cell is the left neighbor of the first cell.

Every neighborhood is repeated numerous times throughout the diagram; evolution is referred to central cells, whose new values can be found in the next line, just below the old cell.

A table of transitions explicitly describes the function mapping each neighborhood of a cell into the cell's next value, but for general discussions or proving theorems it is better to use common mathematical notation. The symbol , or simply , is often reserved to denote this transition function. Of course, such a definition serves only for nearest neighbors; the function would have 2r+1 arguments if it belonged to a automaton.

Either Perry's or Wolfram's representation makes clear how many rules there are, because, given a automaton, any one of the k states can result from the evolution of each of the different neighborhoods. Because of the exponent involved, the number of possibilities increases drastically if either the number of states for a single cell increases, or the number of neighbors increases. Thus a automaton -- three states with nearest neighbors -- has or 27 neighborhoods, and the total number of possible rules would be , somewhere on the order of , so they are not soon going to be studied one by one. Alternatively, the combination would have 32 different neighborhoods, and thus different rules, which is ``only'' in the range of .

To obtain a reasonable sampling of even the smaller linear automata, Wolfram used the idea which was already implicit in Conway's statement of his rule, that the evolutionary criterion should depend on the number of cells in the neighborhood, but not on their particular arrangement. Talking in such terms reveals some hidden assumptions about our vocabulary. In Conway's binary game, zero represented a dead cell, one a live cell, and his rules were stated in terms of the number of live cells in the neighborhood. It is a simple extension of this idea to assign numbers (weights, if you wish) to the states, and make the transition depend only on their sum. A rule gotten this way is called a totalistic rule; not all rules are totalistic, but they lead to a more manageable sampling of all the possible rules.

Curiously, rule 22 cited above is also a totalistic rule. Three binary digits can add up to zero, one, two, or three. If these possibles sums are arranged in descending order as before and paired with the corresponding value of the evolved cell, a totalistic rule number can be derived (which in this case would be decimal 4).

Even the use of the number of distinct sums can lead to very large numbers; also there is a question of whether the evolving cell should have its own weight included or excluded from the sum. For binary automata (but for higher dimensions) Bays has introduced the notation to mean: if the cell is one (alive) and there are between w and x neighbors, it survives; while if is zero and has between y and z neighbors, a cell will be born. In this notation, Conway's original game was a Life .

Doubtless other notations will evolve as significant new combinations requiring them come to light.

Next: Probability theory Up: History Previous: One dimensional automata

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