    Next: The reduced evolution Up: Cycles in space Previous: Cycles for Rule

# The evolution matrix

The evolution of an automaton can be described in matrix form, as well as by the evolution function . The matrix required has to be rectangular, since there are boundary cells at the ends of the string whose evolution cannot be computed from the information available in the string itself. The simplest matrix in the series describes the cells of the second generation in terms of the cells comprising their neighborhoods; two values can evolve from eight neighborhoods {000, 001, 010, 010, 011, 100, 101, 110, 111}, so the required matrix has the dimension ; for Rule 22 it would take the form: where the evident formula for the matrix elements is Since the matrix is not square, successive generations of the evolution cannot be obtained by raising it to powers. However, by iterating it is possible to obtain the matrix for further generations, and thus to relate any pair of generations. Unfortunately such a procedure corresponds to none of the commonly recognized operations on matrices (such as the tensor product).

For example, we might work out, again for Rule 22, the matrix for one generation of evolution of the five-cell neighborhoods which will produce the three-cell neighborhoods which evolve into single cells. Such a matrix would be and finally, going one step further, .

According to this scheme, one has , and a clear procedure for advancing through further generations. Since the dimension of these matrices increases rapidly -- doubling each generation -- and since they have very few non-zero elements, they are of more interest for theoretical discussions than as a practical means of computation. In keeping with the fact that they represent a function, there is exactly one non-zero element in each column, but since they are not square, some rows must necessarily have several non-zero elements. The exact distribution will vary from rule to rule and to a great extent will characterize the rule involved.    Next: The reduced evolution Up: Cycles in space Previous: Cycles for Rule

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