From: McIntosh Harold V.-UAP (mcintosh@redvax1.dgsca.unam.mx)
Date: Fri Jun 25 1993 - 01:41:30 UTC
We continue our commentary on Andrew Wuensche and Mike Lesser's new book,
'The Global Dynamics of Cellular Automata.' Addison-Wesley, 1992 (ISBN
0-201-55740-1). In previous episodes, the role of diagrams in describing
the evolution of automata has been mentioned, especially the evolution
diagram, (of which their computer program generates the nice examples
shown in the Atlas), and the de Bruijn diagram, which they do not mention,
but which can be used to calculate ancestors.
For Wolfram's (2,1) Rule 22, this leads to a pair of 4x4 matrices,
1 0 0 0 0 1 0 0
A = 0 0 0 1 B = 0 0 1 0
0 1 0 0 1 0 0 0
0 0 1 1 0 0 0 0
Note that both are partially diagonal, although in different ways. For A
this says that a zero neighborhood is a counterimage of zero, but then if
you try to extend it, you can't ever have any ones. Of course; ones are
expansive for Rule 22. The other component has maximum eigenvalue 1.459,
which is the growth factor for long configurations which vanish instantly.
The configurations which it generates had better not have pairs of zeroes.
The greatest growth factor for any rule is 2.0, the maximum row or column
sum for these 4x4 de Bruijn matrices.
The second matrix, B, has a cube root of the unit matrix in its upper left
hand corner. This means that you can never use the neighborhood 111 in a
counterimage of pure ones, and that the fragments 01, 10, and 00 must always
run in cyclic order. The eigenvalues of this corner have absolute value 1,
so the number of counterimages of pure 1's is always the same, no matter how
long or short the ring.
In general, it is arbitrary configurations whose ancestors are sought, not
pure strings. However, we know that there is a norm for matrices, related
to the absolute value of their largest eigenvalue, following which the norm
of a product is always less than the product of the norms (but equal when
the factors commute). This means that the state with the largest fraction
of ancestors is always going to get the lion's share of the ancestors,
exponentially following that majority's share of the configuration. So
it is, that configurations in Rule 22 have few ancestors unless they have
lots of zeroes, as we see by turning to page 96 of the Atlas. .
The de Bruijn pair for the famed stochastic Rule 30 is
1 0 0 0 0 1 0 0
A = 0 0 0 0 B = 0 0 1 1
0 1 0 0 1 0 0 0
0 0 1 1 0 0 0 0.
Note that Rule 30 is a one-bit mutant of Rule 22, differing only in the
behavior of neighborhood 011, and thus the assignment of the link 01 - 11.
However, the Perron Eigenvalues of both matrices are 1, so that the number
of ancestors will be expected to remain constant for all configuration
lengths. Compare the attraction basins on page 144 of the Atlas.
Now we have set the stage for thinking of the possible relation of the
Z-parameter and Langton's lambda parameter to the matrices derived from
the de Bruijn diagram. Nevertheless we should introduce the characters
and outline the plot before proceding with the show.
The nodes in the de Bruijn diagram are called 'start strings' in section
3.4.1 of the Atlas, left or right according to the direction of arrows
connecting them. In all ancestor calculations, the possible variety of
start strings lends an ambiguity which tends to persist; reversible rules
are only possible when this ambiguity can be shown to be irrelevant, even
when all the other factors are favorable.
When every row (alternatively, every column) of a de Bruijn diagram contains
a single 1, we have one of the 'limited preimage rules.' By Gerschgorin's
theorem, the eigenvalues of such matrices are bounded by 1 (and according
to Perron, the maximum eigenvalue is exactly 1), all of which is in accordance
with the experience that counterimages not proliferate excessively, thereby
justifying the adjective chosen in the Atlas.
Note that the eigenvalues represent an asymptotic rate of growth, and that
boundary conditions have to be taken into account. Thus there are Gardens of
Eden in the Atlas even when growth factors are unity. Generally we would
expect that if some populations grow, others languish, to maintain constant
the total number of configurations. But in finite systems, the constraints
are more exacting, and can produce an occasional vanishment which might not
be found in an infinite system.
Cyclic boundary conditions correspond to the diagonal of the de Bruijn
matrices, because the 'start string' is the same as the 'stop string.'
Individual matrix elements correspond to chosing one particular start,
and one particular stop. For infinite chains all elements must be
considered, whereas for configurations which are 'quiescent at infinity,'
the (q,q) element is the relevant one (q the quiescent state).
It should be explained that the theory here outlined is inherent in the
Atlas' list of references, particularly in the work of Erica Jen there cited,
and in articles of Stephen Wolfram, also cited. The principal difference is
that Jen's work is phrased in terms of recursion relations, not matrix
theory (although she exhibits them and describes their use). Furthermore,
the nicest theorems do not seem to result from matrix theory alone. The
advantage of a matrix-oriented point of view is that it leads naturally
to eigenvalues and eigenvectors, or whatever it is that they signify in
the particular application. Here, it is rates of growth in the number of
counterimages with respect to the length of the ring of cells. Eigenvectors
are less important (the principal eigenvector can be scaled to get positive
real probabilities), but they would have exact rates of growth.
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:17 UTC