In the first half of this article, we looked at the behavior of cellular automata on infinite lattices. In this final half we will examine some of the properties of CA acting on finite systems, and trace their relationships with properties of infinite-sized systems.
Consider a one-dimensional
cellular automaton operating on periodic lattices of cells
each having two states. If the size of the periodic lattice is s,
then there are 
possible configurations
of cell states on the lattice. Each configuration maps to
a new configuration under the action of the cellular automaton
rule. Thus, we think of the configuration as a node in a graph,
with an out-going arc leading to its successor configuration.
As the number of possible configurations is finite,
any initial configuration must map eventually to a temporally periodic
cycle. Most cellular automata are irreversible.
That is, some configurations have more than
one possible ancestor, so the evolution cannot be run deterministically
backward in time. For these rules the state space (the
set of configurations on the lattice) is thus organized
into a collection sheets, each containing a forest
of trees rooted on a cycle. The leaves of
the trees are the configurations which have no preimages, the
so-called Gardens of Eden. In the opposite
extreme, configurations on cycles
have preimages infinitely far back in time. Configurations on
the branches of the trees have intermediate length
histories.
One way to characterize cellular automata, then, is
by the shape of their transient trees.
To make a connection back to infinite systems, one
can study how these shapes in the limit of size tending to infinity.
For small systems, the state-transition graphs of cellular automata can be represented by a diagram (figure 1). To produce these diagrams, a random initial condition is chosen and iterated until it entered a temporal cycle. Each configuration is represented as a point, and the temporal cycle is show as a ring of points in the center of the diagram. In the next largest concentric ring are show the preimages of the configurations on the cycle, connected to their image by a line segment. The preimages of these are shown in the next concentric circle, and so on.
It is difficult to draw conclusions concerning the ultimate shape of state-transition graphs from diagrams such as shown in figure 1. The structure of small systems tends to be dominated by features which result from the interaction of number-theoretic properties of the system size with properties of the rule table. Large systems, on the other hand, contain too many states to be conveniently displayed in a single image. Nonetheless, figure 1 clearly shows that some rules produce structures which are composed of long, bare trees, while others are composed almost exclusively of leaves. Most have some intermediate structure.
Figure 1: State Transition Diagrams
The most evident feature of a state transition graph is the size of its base cycle and transient trees. A number of studies have aimed to discover laws describing how the size of these features scales with the size of the lattice on which the cellular automaton operates. It appears generally that transient and cycle lengths are constant for simple rules, exponential for chaotic rules, and power-law (or some more exotic scaling) for complex rules. Some evidence [7] suggests that transients and cycles for a given chaotic rule normally scale following the same law, while complex rules may exhibit features which scale in different ways.
One way to understand the origin of these scaling laws is to look at the distribution of transient or cycle lengths for a fixed system size. Figure 2 shows a space-time diagram for two rules, 1) a chaotic rule, nearest-neighbor rule 22, and 2) a complex rule, next-nearest neighbor rule 20. Below each diagram is a plot of the distribution of transient times. The chaotic rule produces a single-peak distribution. The shape of the distribution does not change as the system size increases, so the all statistics of the distribution: average, median, maximum and so on, scale in the same way with system size.
By contrast, the long tails characteristic
of the rule 20 transient time distribution lead to different scaling
behaviors depending on which statistic is chosen. The maximum
transient time scales linearly with respect to system size. This
time is controlled by the time taken for information, in the form
of gliders, to flow across the entire system.
The median transient time, on the other hand, grows only logarithmically
with system size. Most initial
configurations tend rapidly to the 0 configuration, or to a configuration
which contains but a single glider. In these cases, there is effectively
no information flow across the system during the transient.
The average transient time reflects a melange of these effects.
On small systems ( 
),
the average scales like the median.
On larger systems it becomes more common for glider interactions
to contribute to the transient time. Though these events remain
rare, as system size increases they come to
dominate the average. Eventually, the average scales like the maximum.
Figure 2: Distribution of Transient Times
We suggested in the introduction that one of the main services CA can render to complexity theory is to help connect physics to computation theory. One way to apply computation theory to physics is to find a map from the behavior of the physical system onto the operation of a computing machine. Various approaches are described in [4,6]. CA, like many physical systems, are governed by local, translationally invariant, interactions. The connections with computers, in particular parallel computers, derive from considering each cell in the cellular automaton as performing logical operations on its inputs. In the interpretation of CA as computers, problems are posed coded into the initial configuration of cell states on the lattice, and solutions decoded from some configuration ultimately achieved under evolution of the automaton.
One method used in computation theory to characterize the complexity of
a computing machine is to measure
the time it takes the machine to produce an answer to
a problem, at which point the operation of the machine halts.
One studies how this halting time depends on the
length of the problem in some suitable encoding.
We can thus think of a machine composed of the cellular automaton
itself operating on a finite lattice with periodic
boundary conditions, along with some mechanism for
recognizing that a configuration has been visited twice.
The problem posed to this machine is to determine the
projection under the CA rule of the initial configuration
onto the invariant set; otherwise said, the point
at which an initial configuration hits
a cycle.
The machine operates by applying the cellular automaton repeatedly
to an initial configuration until some configuration has been visited twice;
that configuration is the solution.
Any initial configuration must eventually
enter a cycle, hence this machine will always halt.
Topologically, the halting time is simply the size
of the set of configurations, H,
reachable from a given initial configuration.
The cycle time is the size of the largest subset, C, in H
whose image under the rule, 
is equal to
itself, i.e., such that 
. The transient time
is the size of the complement, T, of C in H.
The halting configuration
is then 
, or the initial configuration
itself if it is chosen on a cycle.
These times may thus be discussed independently
of any particular model or method of computation.
However, the program described above
is quite reasonably the shortest which computes the halting configuration
for arbitrary CA on arbitrary initial conditions. Hence, the
halting time is related to the
``logical depth" of the halting configuration.
Grassberger [6] argued that no single quantity is sufficient to measure complexity, since much depends on how meaning is assigned to this term. We wish to emphasize here that even when meaning has been fixed by the definition of an observable quantity, the statistics of the measurement of this observable are crucial to its interpretation. This interpretation emerges in the relationship between the scaling of relevant statistical properties.
For chaotic rules, all measured statistics scale with the same functional form. In complex rules the scaling may depend markedly on which statistic is chosen. Distributions with long tails, such as those characteristic of rule 20, are common in physics. It may be suggested, then, that when computation-theoretic measures of complexity are applied to physical problems, the possibility that averages may not be sufficient measures of distributions (indeed may not exist) should be explicitly taken into account.
The connection between complexity as defined in terms of behavior on finite systems with complexity as defined in terms of the statistical properties of infinite systems is subtle and deserves further exploration. The rules showing exponential growth with system size of topological transients and cycles exhibit rapid convergence to invariant statistical properties both in simulation experiments on large systems and in generalized mean-field approximations. Complex rules, on the other hand, show sub-exponential growth of topological transients, coupled with slow statistical convergence.
The concept of a topological skeleton is meant to reconcile two apparently contradictory sets of results. 1) For most rules the probability that a randomly selected configuration is a Garden of Eden configuration ( i.e. has no preimages) rapidly approaches 1 as the size of the configuration increases. This suggests that state-transition graphs typically contains highly branched transient trees of low depth, since such a structure would have most of its mass in the leaves at the extremities of the graph. On the other hand, and as we have seen above, 2) transient times typically scale exponentially with system size. This suggests a structure with most of its mass in the interior, in the branches and roots.
The topological skeleton hypothesis holds that, in the limit of large system size, the state-transition graph of a chaotic rule consists of an (exponentially elongated) skeleton of configurations with long possible histories, covered by an (exponentially thin and dense) skin of configurations with vanishing histories. This distinction between skeleton and skin is defined in terms of the length of histories. To explore this issue, one must have a method to measure the length of the history of a configuration. One technique to measure histories by means of inverse iteration.
To inverse iterate a cellular automaton, one needs to construct a preimage for the state of the automaton. This can be done efficiently by breaking the configuration into subblocks and piecing together a preimage for the whole configuration from the preimages of the blocks. Under an irreversible rule, configurations typically have either no preimages (are Gardens of Eden) or they have many preimages. If one attempts to backward iterate by choosing a preimage randomly from the set of possible preimages, only a few backward steps can be made before a Garden of Eden is encountered. Thus most backward paths lead directly to a leaf in the state transition graph.
Consider a state produced after many iterations of a cellular automaton. Even though most backward paths from this state are short, it has at least one long backward path. How can this path be found? One approach [8] is to limit search to preimages which are highly probable under the natural measure. The reasoning is as follows: Assume we know the natural measure of the rule. If we take a block from a configuration which has been produced by many iterations of the rule, we may predict its preimage according to the natural measure. One anticipates that a preimage likely according to the natural measure is also likely to have itself a preimage. After all, the natural measure represents the set of configurations with infinite histories, and the configuration under consideration has a long history by construction.
Numerical studies show that the natural measure makes inverse iteration considerably more potent than randomly driven inverse iteration, especially in the case of complex rules. This means that the natural measure helps pick out the (very few) physically relevant preimages from the mass of non-physical states. The resolution of the paradox presented above is a picture by which state transition graphs are composed of two parts, 1) a skeleton of physically relevant states, typically exponentially long, and, in the limit of large system size, of measure zero, and 2) a skin of non-physical, transitional states, comprising the bulk of the nodes in the graph.
In some sense (cf. [1]) the more complex the rule, the more the present state of the system encodes the entire history of its production. The statistical inverse iteration procedure is one general way to exploit this record, albeit imperfectly. Chaotic, relatively uncomplex, rules forget their history. There is little correlation between the past and present state of the system, resulting in a close backward horizon. Complex rules have large information-storage capacity, and use some of this capacity to remember aspects of their previous states.