Cellular automata are dynamical systems in which space, time, and the states of the system are discrete. Each cell in a regular lattice changes its state with time according to a rule which is local and deterministic. All cells on the lattice obey the same rule. Given a randomly-chosen cellular automaton rule, how do we expect it will behave? The following is an informal account of some attempts to answer this question quantitatively.
Wolfram (1983) addressed the issue by dividing cellular automata into four broad, largely qualitative classes: I) very dull (all configurations map to a homogeneous state), II) dull (all configurations map eventually to simple separated periodic structures), III) interesting (produce chaotic patterns, large-time prediction of behavior is impossible, though precise statistical statements may be made), IV) very interesting (produce propagating structures, sometimes soliton-like, may perform useful computations, have behavior which is provably undecideable etc). He indicated that most cellular automata were of the class III variety.
More recently, we have been working to form some more quantitative expectations about what the space of cellular automata contains. Coming from two rather different perspectives, and using rather different techniques, we have arrived at remarkably similar conclusions: most cellular automata are indeed in class III, in the sense that they produce chaotic-looking patterns, but they are hardly ``interesting''. All patterns of cell states over a finite region may occur at large-time, and what's more, occur with probabilty depending only on the size of the region. That is, phase space is uniformly filled, there is no order within chaos, there is simply a random gas of cell states. Even if we input structure into these rules in terms of initial conditions, this structure is destroyed.
We will call such cellular automata dull, but dull for a different reason than the dullness of classes I and II. Not all cellular automata are dull, but most are, and the fraction of rules which are dull rapidly approaches 1 as the size of the neighborhood or the number of possible cell states is increased.
So, if most cellular automata are dull, what makes for ``interestingness'' in cellular automata, and what properties do ``interesting'' cellular automata share?
Cellular automata are interesting when their global behavior is more than the sum of the behaviors of their individual parts: the cells. Thus, the individual cells in interesting CA must interact cooperatively in some fashion in support of the global dynamics. In order to do so, cells must communicate information between themselves in a meaningfull manner.
Class I, II, and most class III CA's are dull precisely because information cannot be transmitted between cells in any meaningfull manner. In classes I and II, information is not transmitted. In most class III CA's, although information is transmitted, it is not transmitted in a useful form, and in fact the generic behavior of this class is very similiar to the behavior of lattices where the values of each site are updated by picking the next state with uniform-random bias over the state set.
In short, Classes I and II exhibit too much inter-cell dependence for useful information processing to take place, and most Class III CA's exhibit too little inter-cell dependence for useful information processing to take place. Too much or too little dependence between cells sets the stage for dull behavior. The criterion for interesting cellular automata, then, is to achieve some sort of tradeoff between too-much and too-little inter-cell dependence.
Although it is true that the generic cellular automaton picked at random is dull, methods exist for generating CA rules that are quite likely to support interesting behavior.
One of these methods (Langton 1988) involves parameterizing the space of CA
rules in such a way that interesting behavior can be ``tuned in'' by twisting
the parameter knob. The parameter used is a simple measure of the distribution
of state transitions in the transition rule. For CA with a symmetric quiescent
condition (homogeneous neighborhoods do not change), we arbitrarily pick one of
the states and call it the reference state . If we let
P(
) be the
percentage of transitions to state
in the rule
table, then we define the parameter lambda as:
. We now use
to
generate random CA transition rules as follows. Pick a value for
and divide the
remaining probability of
equally among the remaining states. Walk through the rule table
filling in the transitions using these probabilities. Thus, for
, all
the transitions save the non-
homogeneous
neighborhoods will be to state
, for
, half of the
transitions will be to state
and the
remaining transitions will be equally distributed among the other states, and
for
,
none of the transitions will be to
, and the other
states will be represented equally in the transition table. Twisting the
knob
generating a series of transition rules and studying the behavior of CA's run
under the rule-tables so-generated is a simple way to search for structure and
interesting regions in CA rule-space.
The measure we use to distinguish interesting from dull CA's is the
mutual information between two cells, and
, separated in
time and/or space. The mutual information is defined as the sum of the entropy
of the individual cells minus the entropy of the joint process:
The mutual information is bounded above by the entropy of the individual
cells. In the case of independent behavior of and
,
and so
. In the case
where
and
are
totally dependent,
so
. Mutual information thus gives a useful handle on the ebb and flow
of information within a CA.
Figure 1 shows the raw data for vs
for
approximately
randomly generated, 2D cellular automata allowing 8 states per
cell. Here, cell
is just cell
one time step
later. The most obvious features are 1) the bimodal distribution and the
approximate range of
where the highest values for
are found, 2)
the sharp convergence toward the extended tail, and 3) the non-zero value of
for high
values of
. Taking these in order, the bimodal distribution reflects the
different classes of automata mentioned above. Classes I and II are found
primarily in the lower cluster, Class III is found primarily in the extended
tail, and Class 4, the interesting class, is found primarily in the humped part
of the upper cluster, i.e., associated with the higher values of
, as one would
expect if interesting behavior depends on the meaningful transmission of
information. The sharp convergence toward the extended tail reflects the
qualitative change in behavior between interesting Class IV behavior to the left
and dull class III behavior to the right. The tightly converged, non-zero value
for
at
the end of the extended tail is characteristic for Class III CA's and might be
referred to as the ``cosmic background mutual information'' in the array, due to
the fact that all of the cells in the array are obeying the same transition
function. It is what is measured even between cells that are separated by large
distances in space under chaotic rules. Subtracting out this background
correlation yields a value very close to zero for most Class III CA's,
consistent with the interpretation that even neighboring cells are effectively
behaving independently.
Another method for cellular automaton engineering (Gutowitz, 1988) involves the mean field theory for cellular automata, and a generalization of the mean field theory, called local structure theory (Gutowitz et al. 1987). Cellular automata are replaced by real-valued recursion equations. These equations are then examined for desired behavior. Finally, a (non-unique) inverse map is applied to find cellular automata which correspond to the selected recursion equations.
The mean field theory is derived from the assumption that no correlations between cell states are generated in the course of cellular automaton evolution. This assumption leads one to associate a simple system of polynomial recursion equations with a cellular automaton. This system of equations gives the probability of each cell state at a given time in terms of the probability of each cell state at the previous time. The roots of equations provide estimates for the large-time probability of each cell state. For present purposes, the fundamental observation is that many distinct cellular automata may lead to the same mean field system of equations. Hence the roots of a given mean field theory expression are estimates for the large-time behavior of all cellular automata which give rise to the expression. By varing parameters in the mean field theory, the behavior of a vast number of cellular automata may be explored in short order. Regions of parameter space which represent rare, interesting, behavior may be located. There are at least two technical challenges: 1) to work backward from a mean field theory expression to the set of rules which give rise to that expression, and 2) to verify that rules which have the same mean field expressions in fact have similar properties.
The method which yields all cellular automata with a given mean field
expression relies on writing these equations as a sum of probabilities of blocks
of a given type, weighted by an integer-valued coefficient. The type of
block depends only on how many cells in each of the possible states it contains.
Let be
the number of blocks of a given type
. The
coefficient,
, indexes the number of blocks of this type which yield a
particular value when the CA rule is applied. To find all the rules which have
mean field expressions with a particular set of coefficients, one must list all
ways of
achieving the values
with subsets of
blocks. Each
way of doing this corresponds to a different cellular automaton rule. The total
number of rules with a given expression is the product over all types
of
Having found
all cellular automata with a given mean field expression, we can empirically
test if they have similar behavior. A summary of a large number of Monte Carlo
experiments in this direction is the following: cellular automata which give
rise to a mean field expression which predicts dull or interesting behavior tend
to be dull or interesting respectively. Still, the mean field theory fails too
often to permit precision engineering.
Improvement of the mean field theory requires that the assumption that no
correlations between cell states are generated by cellular automata be relaxed.
A sequence of generalizations (Gutowitz et al. 1987) of the mean field theory
has been devised in which correlations are represented in terms of the
probability of blocks of length . Whereas the
mean field theory gave the probability of each cell state at a given in terms of
the probability of the cell states at the previous time, the
-th order
generalization gives the probabiltiy of each
-block at a
given time in terms of the probability of the
-blocks at the
previous time. The fixed points of these equations again yield estimates of the
large-time behavior of the cellular automata which gave rise to them. As in the
case of mean field theory, it is possible (though involved) to construct an
inverse map from a high-order theory to the corresponding set of CA. The
high-order theories have several advantages, among them: 1) they yield more
accurate estimates of limiting behavior of individual cellular automata, 2) the
set of cellular automata with a given high-order expression tend to be more
similar to each other than those which mearly share the same mean field
expression, 3) the number of rules which share a high-order expression is
typically smaller than the number of rules which share a given low-order
expression. In short, the higher the order of theory, the more finely and
accurately is the space of cellular automata broken into behavioral classes of
rules. By adjusting the parameters of a high-order theory, it is possible not
only to locate interesting rules, but interesting rules with precisely the
properties desired.
Clearly, applications abound. An application currently being pursued is the design of cellular automata whose natural measure corresponds to the scaling function of given smooth dynamical systems, e.g. golden mean rotation or period-doubling.
We can summarize our results with an analogy which may be taken quite literally. The dullest forms of matter are regular crystals at one end, and ideal gases at the other. In the first case, each atom of the crystal has perfect information about every other atom. In the second case, each molecule of the gas has no information about any other molecule. A small fraction of cellular automata are like crystals, and the bulk of cellular automata are like ideal gases. The analytical methods used to study crystals are applicable to this first set of automata, and the analytical methods used to study gases are applicable to the second set of automata. In particular, the mean field theory is an excellent approximation for many cellular automata.
Between these extremes lie the liquids on one hand, and the interesting
cellular automata on the other. Here correlations between entites exist, but
tend to decay with distance at a finite, but non-zero rate. Entities cooperate
to form macroscopic patterns, often shifting and unstable. The assumptions of
the mean field theory are no longer valid. Analysis must take the sharing of
information between entities into account explicitly. Both methods described
here for the design of cellular automata rely on a breakdown of the
no-mutual-information assumption to signal the presence of an interesting
cellular automaton.
References
H.A. Gutowitz Cellular Automata which Possess a Natural
Measure,
In preparation. (1988).
H.A. Gutowitz, J.D. Victor, B.W. Knight Local Structure Theory
for
Cellular Automata, Physica D 29:18. (1987).
C.G. Langton Structure in Cellular Automaton Rule Space,
In
preparation (1988).
S. Wolfram Statistical Mechanics of Cellular Automata,
Rev. Mod.
Phys. 55:601 (1983).