Commentary related to Andrew Wuensche and Mike Lesser's book, ``The Global Dynamics of Cellular Automata.'' Addison-Wesley, 1992 (ISBN 0-201-55740-1) continues. While referring to this Atlas occasionally, a theory has been elaborated by which the statistical properties of the ancestor distribution for a one-dimensional cellular automaton may be deduced. Presentation of the theory having run its course, interpretation and comparison with the Atlas remains.
The theory which has been presented assigns a prominent role to a quantity
which we have called , which is the average of either the row sums or
the column sums of a matrix. For the connectivity matrices of de Bruijn
matrices, this translates directly into numbers of ancestors, their squares,
and their averages. This is reminiscent of earlier work of Christopher
Langton, who used such averages for classifying automata; strictly his
lambda compared the quiescent state to the rest, but there are only two
states for binary automata. Wuensche and Lesser record lambda for all the
automata in the Atlas, along with Z, a parameter of their own.
What is new in these commentaries is the relationship between variance and
the parameters, namely the rate of growth in the standard deviation which
depends upon , where a is the number of ancestors of 0, b the
number of ancestors of 1, and 16 is the dimension of the pair connection
matrix.
Previously the rate of growth has been tabulated for (2,1) automata; here it is shown for (2,3/2) automata.
In 1972 Amoroso and Patt found
some non-trivial reversible automata amongst the 614 with zero variance. By
non-trivial, one discounts rules which work by shifting, complementing, or
copying, which are the only reversible (2,1) Rules.
Another tabulation which we have made concerns (3,1/2) automata; here we have
a, b, and c with lambda determined by :
In all of these (three) cases which we have presented, some common
features can be observed. Each value of leads to a rather well
defined cluster of growth rates, even though the value of
itself
corresponds to observation better for high values than for low values;
nevertheless the discrepancy is gradual and monotonic.
At one time we thought that there was a gap between zero variance and
the next lower value, but experience with additional (k,r) combinations
has reduced our confidence in its existence; it is most likely an artifact
of small sample size (small k, small r). The general shape of the histogram
ought to be roughly Gaussian, because of the binomial coefficients associated
with given values of , which itself grows quadratically with a. Actually,
because of
, the purported gaussian is folded over in the middle, ab
giving the same data as ba.
Since a Gaussian has a point of inflection at its own standard deviation,
we would expect a noticeable division of into low values all of whose
Rules have a slow growth rate in their ancestral variance, and those for
large growth rates, up in the tail of the Gaussian. It shouldn't be hard to
figure out this distribution function, but we haven't done it. What we do
notice, is that the growth factor is pretty much the same for quite a few
nearly balanced Rules, and that they are set off slightly from the exactly
balanced Rules.
With respect to interpreting the Atlas, some additional work is called for. The analysis of variance which we have described ultimately translates into an average number of ancestors per configuration, and the growth of this average with respect to the length of the configuration. The Atlas only tabulates the maximum number of counterimages by basin; but it is the average number which follows more readily from our analysis. The average can be deduced by examining the images, but getting a good sample is going to be laborious.
On the other hand, it is instructive to make comparisons of the maximum number of counterimages, particularly as it depends on the lambda parameter.
More commentary will follow.