Problem 5

What invariants are there in cellular automaton evolution?

The existence of invariants or conservation laws in the evolution of a cellular automaton would imply a partitioning of its state space, much as energy provides a partitioning of the state space for Hamiltonian (energy-conserving) dynamical systems. For some class 1 and 2 cellular automata it is straightforward to identify invariants. In other cases, one can specifically construct cellular automaton rules that exhibit certain conservation laws [16--18]. For example, the cellular automata may evolve as if on several disjoint spatial lattices. Or they may support a set of persistent structures or ``particles'' that interact in simple ways. But in general, the identification of numerical invariants in cellular automata will probably be as difficult as it is in other non-linear dynamical systems.

It is nevertheless often possible to find partitionings of the state space for a cellular automaton that are left invariant by its evolution. The partitionings may be formed for example from sets of configurations corresponding to particular regular formal languages (cf. [7]). For example, the set of configurations with a particular period under a cellular automaton mapping is invariant, and in one dimension forms a finite-complement regular language (or ``subshift of finite type''). Different elements in such partitionings may be considered to carry different values of what is often an infinite set of conserved quantities.

A particular cellular automaton rule usually evolves to give qualitatively similar behaviour from almost all initial states (each site is chosen to have each of the possible values with equal probabilities). Often there are sets of initial states that occur with probability zero (for example, states in which all sites have the same value) that evolve differently from the rest. Such states may be distinguished by invariant or conserved quantities. But most initial states evolve to configurations with the same statistical properties. This suggests that even if the possible states could be partitioned according to the value of some invariant, they would be essentially equivalent. It remains conceivable, however, that there exist cellular automata in which two sets of initial states that occur with nonzero probabilities could lead to two qualitatively different forms of behaviour.

previous  l  next