1. Introduction

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.

[ Figure 1 ] Example of evolution of a one-dimensional cellular automaton with two possible values at each site. Configurations at successive time steps are shown as successive lines. Sites with value one are black; those with value zero are left white. The cellular automaton rule illustrated here takes 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. This rule is represented by the polynomial , and is discussed in detail in Sect. 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 [1], where extensive references were given. This paper details and extends the discussion of global properties of cellular automata given in [1]. These global properties may be described in terms of properties of the state transition graphs corresponding to the cellular automata.

[ Figure 2 ] Global state transition diagrams for finite cellular automata with size and periodic boundary conditions evolving according to the rule , as used in Fig. 1, and discussed extensively in Sect. 3. Each node in the graphs represents one of the possible configurations of the sites. The directed edges of the graphs indicate transitions between these configurations associated with single time steps of cellular automaton evolution. Each cycle in the graph represents an ''attractor'' for the configurations corresponding to the nodes in trees rooted on it.

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 [2], [3]. Despite their amenability to algebraic analysis, additive cellular automata exhibit many of the complex features of general cellular automata.

[ Figure 3 ] Evolution of cellular automata with sites arranged in a circle (periodic boundary conditions) according to the rule (as used in Fig. 1 and discussed in Sect. 3). Finite cellular automata such as these ultimately enter cycles in which a sequence of configurations are visited repeatedly. This behaviour is evident here for , , and . For , the cycle has length .

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.

previous  l  next