In the simplest case, a cellular automaton consists of a line of sites with each site carrying a value 0 or 1. The site values evolve synchronously in discrete time steps according to the values of their nearest neighbours. For example, the rule for evolution could take the value of a site at a particular time step to be the sum modulo two of the values of its two nearest neighbours on the previous time step. Figure 1 shows the pattern of nonzero sites generated by evolution with this rule from an initial state containing a single nonzero site. The pattern is found to be self-similar, and is characterized by a fractal dimension . Even with an initial state consisting of a random sequence of 0 and 1 sites (say each with probability ), the evolution of such a cellular automaton leads to correlations between separated sites and the appearance of structure. This behaviour contradicts the second law of thermodynamics for systems with reversible dynamics, and is made possible by the irreversible nature of the cellular automaton evolution. Starting from a maximum entropy ensemble in which all possible configurations appear with equal probability, the evolution increases the probabilities of some configurations at the expense of others. The configurations into which this concentration occurs then dominate ensemble averages and the system is ''organized'' into having the properties of these configurations. A finite cellular automaton with sites (arranged for example around a circle so as to give periodic boundary conditions) has possible distinct configurations. The global evolution of such a cellular automaton may be described by a state transition graph. Figure 2 gives the state transition graph corresponding to the cellular automaton described above, for the cases and . Configurations corresponding to nodes on the periphery of the graph are seen to be depopulated by transitions; all initial configurations ultimately evolve to configurations on one of the cycles in the graph. Any finite cellular automaton ultimately enters a cycle in which a sequence of configurations are visited repeatedly. This behaviour is illustrated in Fig. 3.
Cellular automata may be used as simple models for a wide variety of physical, biological and computational systems. Analysis of general features of their behaviour may therefore yield general results on the behaviour of many complex systems, and may perhaps ultimately suggest generalizations of the laws of thermodynamics appropriate for systems with irreversible dynamics. Several aspects of cellular automata were recently discussed in , where extensive references were given. This paper details and extends the discussion of global properties of cellular automata given in . These global properties may be described in terms of properties of the state transition graphs corresponding to the cellular automata.
This paper concentrates on a class of cellular automata which exhibit the simplifying feature of ''additivity''. The configurations of such cellular automata satisfy an ''additive superposition'' principle, which allows a natural representation of the configurations by characteristic polynomials. The time evolution of the configurations is represented by iterated multiplication of their characteristic polynomials by fixed polynomials. Global properties of cellular automata are then determined by algebraic properties of these polynomials, by methods analogous to those used in the analysis of linear feedback shift registers , . Despite their amenability to algebraic analysis, additive cellular automata exhibit many of the complex features of general cellular automata.
Having introduced notation in Sect. 2, Sect. 3 develops algebraic techniques for the analysis of cellular automata in the context of the simple cellular automaton illustrated in Fig. 1. Some necessary mathematical results are reviewed in the appendices. Section 4 then derives general results for all additive cellular automata. The results allow more than two possible values per site, but are most complete when the number of possible values is prime. They also allow influence on the evolution of a site from sites more distant than its nearest neighbours. The results are extended in Sect. 4D to allow cellular automata in which the sites are arranged in a square or cubic lattice in two, three or more dimensions, rather than just on a line. Section 4E then discusses generalizations in which the cellular automaton time evolution rule involves several preceding time steps. Section 4F considers alternative boundary conditions. In all cases, a characterization of the global structure of the state transition diagram is found in terms of algebraic properties of the polynomials representing the cellular automaton time evolution rule.
Section 5 discusses non-additive cellular automata, for which the algebraic techniques of Sects. 3 and 4 are inapplicable. Combinatorial methods are nevertheless used to derive some results for a particular example.
Section 6 gives a discussion of the results obtained, comparing them with those for other systems.