From: McIntosh Harold V.-UAP (mcintosh@redvax1.dgsca.unam.mx)
Date: Thu Jul 08 1993 - 01:52:03 UTC
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 gamma, 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 (a^2+b^2)/16, 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.
observed second observed
ab number gamma average moment variance
-- ------ --------- -------- ------ --------
0-16 1 4.000 4.000 16.00 0.000
1-15 16 3.531 3.515 12.36 0.088
2-14 120 3.125 3.116 9.73 0.132
3-13 560 2.781 2.797 7.84 0.133
4-12 1820 2.500 2.548 6.51 0.120
5-11 4368 2.281 2.361 5.58 0.104
6-10 8008 2.125 2.231 4.98 0.091
7- 9 11440 2.031 2.154 4.65 0.091
8- 8 12870 2.000 2.129 4.54 0.093
>2.0 12256 2.000 2.135 4.57 0.091
=2.0 614 2.000 2.000 4.000 0.000
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 (a^2+b^2+c^2)/9:
abc number min max sigma ave gamma
--- ------ ----- ----- ----- ----- -----
009 1 9.000 9.000 0.000 9.000 9.000
018 9 7.047 7.519 0.222 7.204 7.222
027 36 5.747 6.110 0.164 5.949 5.889
036 84 5.000 5.531 0.163 5.107 5.000
045 126 4.562 5.266 0.133 4.676 4.556
117 72 5.095 6.002 0.334 5.704 5.667
126 252 4.362 5.283 0.254 4.719 4.556
135 504 3.813 4.615 0.227 4.121 3.889
144 630 3.707 4.854 0.213 3.920 3.667
225 756 3.707 4.854 0.242 3.970 3.667
234 1260 3.259 5.000 0.248 3.602 3.222
333 1680 3.000 4.002 0.298 3.430 3.000
>0.0 1260 0.197 3.547 3.000
=0.0 420 0.000 3.000 3.000
In all of these (three) cases which we have presented, some common
features can be observed. Each value of gamma leads to a rather well
defined cluster of growth rates, even though the value of gamma 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 gamma, which itself grows quadratically with a. Actually,
because of a^2+b^2, 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 noticable division of gamma 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.
Harold V. McIntosh |Depto. de Aplicaci'on de Microcomputadoras
mcintosh@redvax1.dgsca.unam.mx |Instituto de Ciencias/UAP
mcintosh@redvax1.bitnet |Apdo. Postal 461
(+52+22)43-6330 |72000 Puebla, Pue., MEXICO
This archive was generated by hypermail 2.1.7 : Tue Oct 14 2003 - 21:44:18 UTC