From: McIntosh Harold V.-UAP (mcintosh@redvax1.dgsca.unam.mx)
Date: Tue Jul 13 1993 - 02:49:58 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. At least two different parameters, lambda and Z, are useful in
classifying cellular automata; but the general philosophy of parameters
should be contemplated before deciding to rely on one or another of them,
or on something else.
It is a natural idea to assign a single number to an automaton, or to an
automaton rule, with the expectation that it will distinguish between
automata, and perhaps also reveal some significant information about them.
An extermely natural and obvious candidate is the fraction of transitions
(or neighborhoods, if you wish) leading to one of the states, particularly
in a binary automaton.
From the side of probability theory, one expects an automaton to evolve
into an equilibrium in which the fraction of neighborhoods producing the
state is the same as the relative proportion of that state. In its simplest
application, this is mean field theory, but other approaches utilize varying
degrees of sophistication for estimating the probabilities, making for
correspondingly better estimates. The fraction of neighborhoods serves as
an excellent starting point for these theories, and is often not too far
from the equilibrium calculated by other theories.
From the side of ancestor theory, we have seen that there are some matrices
arising from graph theory, whose spectral radii and spectral norms, between
them, account for the proliferation of ancestors, which is the converse of
the convergence seen during evolution. We have also seen that the ancestor
fraction serves to give a reasonable estimate of the growth rate, not of
ancestors from generation to generation, but of the number of ancestors for
a single generation as a function of the length of a configuration.
Indirectly these estimates affect the characteristics of the evolution for
many generations, which are thereby related to the underlying parameter.
Thus a parameter may serve for more than classification, it may participate
in some simple algabraic expression describing observable data produced by
the automaton. When a parameter enjoys a general display of success, the
public seems to become more demanding in its expectations for the parameter,
demanding either a new and better parameter, or some supplementary parameters
which explain discrepancies in the predictions of the original paramenter.
With respect to the calculation of ancestors, there is a good and solidly
based theory from which to start. The de Bruijn diagram, and such of its
subsidiaries as the subset diagram, pair diagram, union diagram, and so on,
allow an exact calculation of ancestors, and statics of ancestors, such
as their average number, standard deviation, and, through their moments,
their exact frequency distribution. In practice, the matrices are large,
the calculations tedious, and above all, symbolic results are desired
which apply to whole classes of automata, rather than just individual
cases.
The procedure would be easier were it not for the discrepancy between
spectral norm and spectral radius, but in general terms, estimating the
largest eigenvalue of the larger of the de Bruijn fragments is sufficient
to estimate the largest number of ancestors that any single configuration
can possibly have, which is a quantity of interest that is tabulated in
the Atlas.
The average number of ancestors is always necessarily 4, for (2,1) automata,
but the actual number is influenced, especially for configurations of short
length, by boundary conditions, and by the variance, which can be estimated
by the same procedures using another matrix (the pair matrix). The actual
distribution is highly skewed, because half of the configurations, in some
sense, have 4 or less ancestors. This quantity includes zero ancestors -
Garden of Eden configurations - and is just as inevitable as the average
of 4.
Not only is the top half of the distribution highly skewed - spread over
the range (4, 2^n) - but it typically contains a few outliers with the
bulk of the data closer to the mean; the standard deviation has to take
this into account.
The outliers are typically the ancestors of the quiescent state, if there
IS one. Modifications in this observation have to be made when there are
TWO quiescent states, or none, or the state with the majority of ancestors
is not the quiescent state (for non-binary automata the permutations
increase quite rapidly with the number of states).
In previous commentaries, we have shown that both Langton's lambda and
Wuensche and Lesser's Z have can be incorporated into formulas expressing
the rate of growth of 'maximal preimaging ' (beware - lambda is gamma and
vv).
(Langton) lambda = gamma + n sigma(c) sigma(x) cos(theta)
(W & L) lambda = 1 + 2n sqrt(1-Z) sqrt(0.5*s^2 + .01561) cos(theta*)
There is nothing especial to reccomend these formulas except that they
are extremely simple; in the Langton version, the second term is simply
ignored. Nevertheless the results agree to about 10%, while the acurately
computed eigenvalues agree quite well with data taken from the Atlas.
To satisfy curiosity regarding the composition of the discarded term, it
is tabulated below for the ab values 08, 17, 26, and 15, according to
Wuensche and Lesser's clusters, all of whose members obey the same statistics.
rule lambda = gamma + n * sigma(c) * sigma(x) * cos(theta) (th) page
---- ----------------------------------------------------------- ----
08 0 2.000 = 2.000 + 4 * 0.000 * 0.000 * 1.000 ( 0) 85
17 2 1.620 = 1.750 + 4 * 0.433 * 0.083 * -0.897 ( 154) 126
1 1.839 = 1.750 + 4 * 0.433 * 0.055 * 0.936 ( 21) 86
4 1.754 = 1.750 + 4 * 0.433 * 0.049 * 0.056 ( 87) 88
26 3 1.617 = 1.500 + 4 * 0.5 * 0.156 * 0.378 ( 68) 128
5 1.615 = 1.500 + 4 * 0.5 * 0.084 * 0.686 ( 47) 90
6 1.470 = 1.500 + 4 * 0.5 * 0.165 * -0.092 ( 95) 130
9 1.338 = 1.500 + 4 * 0.5 * 0.178 * -0.456 ( 117) 134
10 1.166 = 1.500 + 4 * 0.5 * 0.271 * -0.613 ( 127) 161
12 1.100 = 1.500 + 4 * 0.5 * 0.330 * -0.619 ( 128) 136
18 1.613 = 1.500 + 4 * 0.5 * 0.153 * 0.375 ( 68) 92
24 1.100 = 1.500 + 4 * 0.5 * 0.204 * -1.000 ( 180) 169
33 1.465 = 1.500 + 4 * 0.5 * 0.072 * -0.241 ( 103) 100
36 1.617 = 1.500 + 4 * 0.5 * 0.059 * 1.000 ( 0) 103
126 1.617 = 1.500 + 4 * 0.5 * 0.059 * 1.000 ( 0) 123
35 193 1.324 = 1.250 + 4 * 0.433 * 0.158 * 0.279 ( 74) 157
22 1.459 = 1.250 + 4 * 0.433 * 0.163 * 0.744 ( 42) 96
37 1.380 = 1.250 + 4 * 0.433 * 0.086 * 0.845 ( 32) 104
50 1.000 = 1.250 + 4 * 0.829 * 0.165 * -0.454 ( 117) 106
73 1.310 = 1.250 + 4 * 0.433 * 0.144 * 0.262 ( 75) 112
94 1.200 = 1.250 + 4 * 0.433 * 0.065 * -0.365 ( 111) 118
7 1.465 = 1.250 + 4 * 0.433 * 0.169 * 0.738 ( 42) 132
13 1.000 = 1.250 + 4 * 0.433 * 0.433 * -0.333 ( 109) 138
26 1.083 = 1.250 + 4 * 0.433 * 0.299 * -0.333 ( 109) 140
35 1.000 = 1.250 + 4 * 0.829 * 0.250 * -0.301 ( 108) 146
38 1.105 = 1.250 + 4 * 0.829 * 0.203 * -0.229 ( 103) 148
41 1.083 = 1.250 + 4 * 0.433 * 0.299 * -0.333 ( 109) 150
62 1.324 = 1.250 + 4 * 0.433 * 0.158 * 0.279 ( 74) 156
11 1.062 = 1.250 + 4 * 0.433 * 0.333 * -0.228 ( 103) 162
14 1.083 = 1.250 + 4 * 0.433 * 0.345 * -0.289 ( 107) 164
25 1.083 = 1.250 + 4 * 0.829 * 0.299 * -0.174 ( 100) 170
28 1.000 = 1.250 + 4 * 0.433 * 0.259 * -0.555 ( 124) 172
19 1.618 = 1.250 + 4 * 0.829 * 0.156 * 0.710 ( 45) 94
44 29 1.000 = 1.000 + 4 * 0.707 * 0.144 * 0.000 ( 90) 174
ab 1.617 = 1.250 + 4 * 1.089 * 0.160 * 0.526 ( 58) 174
ba 1.618 = 1.250 + 4 * 0.829 * 0.156 * 0.710 ( 45) 174
In earlier commentaries, we have remarked on the excellent agreement between
the eigenvalues and data in the Atlas. Even the three 26 cases which were
judged to be marginal conform quite well to the predictions; we were much
too hasty in our earlier conclusion, due to the large number of small basins
and the closeness of the growth factors to 1.0.
Nevertheless, the agreement begins to suffer with the 35 and 44 automata, for
reasons which answer an earlier question. 44 is balanced, yet does not always
produce zero variance (a known failing). The answer is that the de Bruijn
fragments are strongly attractive and dissipative, hence the matrix has
Jordan form, and the eigenvalue differs markedly from the spectral norm.
It will be seen that the products AB and BA behave better, and give maximal
preimaging consistent with the configurations 01010101.... shown in the Atlas,
whilst the chains 0000... and 1111... may have rather few counterimages.
The single 44 example in the table illustrates what has happened. The spectral
norm of the fragments is sqrt(2) = 1.414, but their eigenvalue is 1. While the
eigenvalue underestimates general growth rates, the spectral norm overestimates
them, given that the true result is sqrt(1.617).
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