Table 13: Finite Lattice State Transition Diagrams

State transition diagrams for cellular automata on finite size lattices.

A cellular automaton on a finite lattice with sites has a total of possible states. The complete evolution of such a cellular automaton can be represented by a finite diagram which shows the possible transitions between these states. Each node in the diagram corresponds to a complete configuration or state of the finite cellular automaton. A directed arc leads from each such node to its successor under one time step of cellular automaton evolution. The possible time sequences of configurations in the complete evolution of the cellular automaton then correspond to possible paths through the directed graph thus formed.

After a time of at most steps, a finite cellular automaton must always enter a cycle, periodically visiting a fixed set of states. In general, the complete state transition diagram contains a number of distinct cycles.

The table shows the fragment of the state transition diagram associated with the longest cycle, for all inequivalent , rules. Results are given for lattices of sizes , and . In all cases, the lattices are taken to have periodic boundary conditions, as if their sites were arrranged in a circle.

The table also gives the lengths and multiplicities of all the cycles for each rule. (The notation used is , representing cycles of length .) Notice that the state transition diagram fragments associated with different cycles of the same length may not be identical. When there are several cycles of maximal length, the fragment shown is the one involving the largest total number of states.

State transition diagram fragments have the general form of cycles fed by trees. The cellular automaton always reaches the cycle after a sufficiently long time. The trees represent transients, and contain states which can occur only after a limited number of time steps. Such transient phenomena are a manifestation of irreversibility in the cellular automaton evolution.

Some finite cellular automata, such as rule 13, are reversible, so that their state transition diagrams contain no transients, and all states are on cycles.

In some other cases, such as rule 90, highly regular state transition diagrams are obtained, containing for example only balanced trees (see pages 159--202 in this book). Many rules, however, yield complicated state transition diagrams.

In the pictures given, individual nodes are not indicated. Nevertheless, the arcs joining nodes are all of equal length in a particular diagram. The overall scale of each diagram can be deduced from the total cycle length given.

The constraint of equal length in some cases forces arcs to intersect in the diagram. In some cases, there are dense areas containing large numbers of arcs. For highly irreversible rules, such as rule 0, large numbers of arcs converge on a single node, and appear essentially as a filled black circle.

Notice that the results given here and in table 14 for cellular automata on finite lattices with periodic boundary conditions also apply to infinite cellular automata in which only spatially periodic configurations are considered.

Table by Holly Peck (Los Alamos National Laboratory).

previous  l  next