2. Notation and Formalism

is taken to denote the value of site in a one-dimensional cellular automaton at time step . Each site value is specified as an integer in the range 0 through . The site values evolve by iteration of the mapping

is an arbitrary function which specifies the cellular automaton rule.

The parameter in eq. (2.1) determines the ``range'' of the rule: the value of a given site depends on the last values of a neighbourhood of at most sites. The region affected by a given site grows by at most sites in each direction at every time step; propagating features generated in cellular automaton evolution may therefore travel at most sites per time step. After time steps, a region of at most sites may therefore be affected by a given initial site value.

The ``elementary'' cellular automata considered in ref. 1 have and , corresponding to nearest-neighbour interactions.

An alternative form of eq. (2.1) is

where the are integer constants, and the function takes a single integer argument. Rules specified according to (2.1) may be reproduced directly by taking .

The special class of additive cellular automaton rules considered in ref. 2 correspond to the case in which is a linear function of its argument modulo . Such rules satisfy a special additive superposition principle. This allows the evolution of any initial configuration to be determined by superposition of results obtained with a few basis configurations, and makes possible the algebraic analysis of ref. 2.

``Totalistic'' rules defined in ref. 1, and used in several examples below, are obtained by taking

in eq. (2.2). Such rules give equal weight to all sites in a neighbourhood, and imply that the value of a site depends only on the total of all preceding neighbourhood site values. The results of section 3 suggest that totalistic rules exhibit behaviour characteristic of all cellular automata.

Cellular automaton rules may be combined by composition. The set of cellular automaton rules is closed under composition, although composition increases the number of sites in the neighbourhood. Composition of a rule with itself yields patterns corresponding to alternate time steps in time evolution according to the rule. Compositions of distinct rules do not in general commute. However, if a composition of rules generates a sequence of configurations with period , then the rule must also allow a sequence of configurations with period . As discussed below, this implies that the rules and must yield behaviour of the same class.

The configuration may be considered as a special ``null'' configuration (``ground state''). The requirement that this configuration remain invariant under time evolution implies

and

All rules satisfy this requirement if iterated at most times, at least up to a relabelling of the possible values.

It is convenient to consider symmetric rules, for which

Once a cellular automaton with symmetric rules has evolved to a symmetric state (in which for some and all ), it may subsequently generate only symmetric states (assuming symmetric boundary conditions), since the operation of space reflection commutes with time evolution in this case.

Rules satisfying the conditions (2.4) and (2.5) will be termed ``legal''.

The cellular automaton rules (2.1) and (2.2) may be considered as discrete analogues of partial differential equations of order at most in space, and first order in time. Cellular automata of higher order in time may be constructed by allowing a particular site value to depend on values of a neighbourhood of sites on a number of previous time steps. Consideration of ``effective'' site values always allows equivalent first-order rules with to be constructed.

The form of the function in the time evolution rule (2.1) may be specified by a ``rule number'' [1]

The function in eq. (2.2) may similarly be specified by a numerical ``code''

The condition (2.4) implies that both and are multiples of .

In general, there are a total of possible cellular automaton rules of the form (2.1) or (2.2). Of these, are legal. The rapid growth of the number of possible rules with implies that an exponentially small fraction of rules may be obtained by composition of rules with smaller .

A few cellular automaton rules are ``reducible'' in the sense that the evolution of sites with particular values, or on a particular grid of positions and times, are independent of other site values. Such cellular automata will usually be excluded from the classification described below.

Very little information on the behaviour of a cellular automaton can be deduced directly from simple properties of its rule. A few simple results are nevertheless clear.

First, necessary (but not sufficient) conditions for a rule to yield unbounded growth are

for some set of . If these conditions are not fulfilled then regions containing nonzero sites surrounded by zero sites can never grow, and the cellular automaton must exhibit behaviour of class 1 or 2. For totalistic rules, the condition (2.8) becomes

for some .

Second, totalistic rules for which

for all exhibit no ``growth inhibition'' and must therefore similarly be of class 1 or 2.

One may consider cellular automata both finite and infinite in extent.

When finite cellular automata are discussed below, they are taken to consist of sites arranged around a circle (periodic boundary conditions). Such cellular automata have a finite number of possible states. Their evolution may be represented by finite state transition diagrams (cf. [2]), in which nodes representing each possible configuration are joined by directed arcs, with a single arc leading from a particular node to its successor after evolution for one time step. After a sufficiently long time (less than ), any finite cellular automaton must enter a cycle, in which a sequence of configurations is visited repeatedly. These cycles represent attractors for the cellular automaton evolution, and correspond to cycles in the state transition graph. At nodes in the cycles may be rooted trees representing transients. The transients are irreversible in the sense that nodes in the tree have a single successor, but may have several predecessors. In the course of time evolution, all states corresponding to nodes in the trees ultimately evolve through the configurations represented by the roots of the trees to the cycles on which the roots lie. Configurations corresponding to nodes on the periphery of the state transition diagram (terminals or leaves of the transient trees) are never reached in the evolution: they may occur only as initial states. The fraction of configurations which may be reached after one time step in cellular automaton evolution, and which are therefore not on the periphery of the state transition diagram, gives a simple measure of irreversibility.

The configurations of infinite cellular automata are specified by (doubly) infinite sequences of site values. Such sequences are naturally identified as elements of a Cantor set (e.g. [3]). (They differ from real numbers through the inequivalence of configurations such as and ). Cellular automaton rules define mappings from this Cantor set to itself. The mappings are invariant under shifts by virtue of the identical treatment of each site in eqs. (2.1) and (2.2). With natural measures of distance in the Cantor set, the mappings are also continuous. The typical irreversibility of cellular automaton evolution is manifest in the fact that the mapping is usually not injective, as discussed in section 4.

Equations (2.1) and (2.2) may be generalized to several dimensions. For , there are at least two possible symmetric forms of neighbourhood, containing (type I) and (type II) sites respectively; for larger other ``unit cells'' are possible.

previous  l  next