From: McIntosh Harold V.-UAP (mcintosh@redvax1.dgsca.unam.mx)
Date: Fri Jul 02 1993 - 02:17:49 UTC
Commentary on Andrew Wuensche and Mike Lesser's new book, 'The Global Dynamics
of Cellular Automata.' Addison-Wesley, 1992 (ISBN 0-201-55740-1) continues. We
have digressed into some issues of matrix theory and graph theory in the
expectation that a better understanding of the foundations of cellular
automaton theory will help with understanding some of the topics of the book,
such as Langton's parameter, Z, and perturbations (mutations).
To maintain a connection with the book, consider again the A and B matrices
for Wolfram's (2,1) Rule 22:
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
For a chain of three cells, we have eight products of these three matrices,
corresponding to the ancestors of 000, 001, 010, and so on:
1 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0
AAA = 0 1 1 1 AAB = 1 0 0 0 ABA = 0 0 0 0 ABB = 0 0 1 0
0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0
0 1 1 2 1 0 1 0 1 0 0 0 0 1 0 0
0 0 1 1 0 0 0 0 0 1 0 0 1 0 0 0
BAA = 0 0 0 1 BAB = 0 0 1 0 BBA = 1 0 0 0 BBB = 0 1 0 0
1 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
From these matrices we draw conclusions about the number of ancestors by
looking at the (0,0) elements (quiescent-at-infinity configurations), traces
(periodic configurations) or summing all the elements in the matrix
(unrestricted configurations):
cells quiescent periodic general (= types of ancestors)
000 1 5 10
001 0 0 4
010 0 0 3
011 0 0 3
100 0 0 4
101 0 0 2
110 0 0 3
111 1 3 3
--- - - --
sum 2 8 32
Turning to page 96 of the Atlas, we confirm that s=8 (sum of the 'periodic'
column) and mp=5 (largest number in the 'periodic' column). The only branching
ratios are 3 and 5 (and of course, 0), confirmed by examining the diagram at
level 3. The fact that g=6 (GOE configurations) follows from the fact that six
of the matrices have zero diagonal, and hence trace zero.
None of the matrices is identically zero, so there are no poison words of
length 3; however, the fact that the multiplicities are not uniform goes
against the theorem (not yet discussed) about nonuniform multiplicities
implying a Garden of Eden.
These details relate to a tiny fraction of the information contained in the
Atlas, but they should suffice to establish the fact that as long as one is
prepared to multiply A and B matrices, several different types of ancestors
can be counted. Also, if one is prepared to work with symbolic matrices
rather than numerical matrices, quite explicit ancestors can be calculated.
Of course, what is really wanted are general theorems about the matrices, so
that all their products DON'T have to be calculated explicitly.
Considerable space would be consumed by listing all eight tensor squares,
but the next point can probably be made with just one of them:
1 . . . | . . . . | . . . . | . . . .
. 1 1 1 | . . . . | . . . . | . . . .
. . 1 1 | . . . . | . . . . | . . . .
. 1 1 2 | . . . . | . . . . | . . . .
-------------------------------------
. . . . | 1 . . . | 1 . . . | 1 . . .
. . . . | . 1 1 1 | . 1 1 1 | . 1 1 1
. . . . | . . 1 1 | . . 1 1 | . . 1 1
. . . . | . 1 1 2 | . 1 1 2 | . 1 1 2
AAAxAAA = -------------------------------------
. . . . | . . . . | 1 . . . | 1 . . .
. . . . | . . . . | . 1 1 1 | . 1 1 1
. . . . | . . . . | . . 1 1 | . . 1 1
. . . . | . . . . | . 1 1 2 | . 1 1 2
-------------------------------------
. . . . | 1 . . . | 1 . . . | 2 . . .
. . . . | . 1 1 1 | . 1 1 1 | . 2 2 2
. . . . | . . 1 1 | . . 1 1 | . . 2 2
. . . . | . 1 1 2 | . 1 1 2 | . 2 2 4
Note the following comparisons:
(0,0) element trace overall sum
AAA 1 5 10
AAAxAAA 1 25 100.
In each case, the corresponding quantity is squared in the tensor square.
Examining the structure of the matrix, it isn't hard to see why. However,
this should give a graphic illustration of why the tensor powers participate
in the calculation of moments, and how the tensor square (the connectivity
matrix of the pair diagram) will eventually be involved in calculating the
variance. Note that if we want to establish zero variance, it is only
necessary to compare the square of the first moment with the second moment.
What is needed is (AxA+BxB)^n; when the power is expanded and all the terms
collected, one finds one term for the square of the number of ancestors of
each configuration. To get the third moment, take (AxAxA+BxBxB)^n, whereas
if there were three states, there would be a C matrix, with a second moment
expressed in terms of (AxA+BxB+CxC)^n, and so on.
Because of the powers, we are interested in the rate of growth of the terms
in parentheses in the last paragraph, which boils down to finding their
largest eigenvalues or more generally, finding estimates or bounds for them.
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