Date: Sun, 5 May 1996 20:24
To: ca@think.com
To create a background against which to review the new books, we hope to be forgiven for including certain articles future and articles present to supplement those articles past which have already been discussed, or whose existence might require mention.
Cristopher Moore <moore@gila.santafe.edu> has announced:
> ...
> \title{Quasi-Linear Cellular Automata} [April 26, 1996]
> ...
> and the other one:
>
> \title{Non-Abelian Cellular Automata} [September 29, 1995]
as well as another which seems to be available at the same place:
\title{Algebraic Properties of the Block
Transformation on Cellular Automata} [October 3, 1995]
Although the abstracts of (at least two of) these articles profess a concern with computational complexity, examination of the articles themselves would disclose a large variety of schemes for the symbolic realization of cellular automaton evolution, principally via the exhibition of numerous algebraic systems for which relationships like the binomial theorem hold. Anyway, they contain a nice exposition of these ideas.
All three of Moore's preprints refer to the following two articles:
Kari Eloranta
Partially permutive cellular automata
Nonlinearity 6 1009-1023 (1993)
Kari Eloranta
Random walks in cellular automata
Nonlinearity 6 1025-1036 (1993)
which are in reality one long article split into shorter pieces. Besides the fact that Eloranta also uses blocking transformations to reduce the analysis to two-neighbor automata, and makes some use of the fact that the resultant binary mapping includes many algebraic systems of interest, our attention is drawn to the relationship between "partial permutivity" and Welch's indices. The first paper is combinarital and introduces subalphabets; the second is concerned with the statistics of kink diffusion..
Wolfram surveyed linear cellular automata looking for characteristic features of their evolution, summarizing part of his insight by describing four Classes. He also noticed that many automata formed membranes, bounding macrocells within which the evolution had to fall into cycles because of their finite extent and fixed boundary conditions. There are shifting macrocells as well as semipermeable membranes, altogether leaving another specialized class of automata whose particular properties could be studied in greater detail.
Just as de Bruijn diagrams can be used to calculate periodic configurations of a cellular automaton by looking for the loops, it is also possible to look for unbranching paths which are bounded by saturated nodes, from which the membranes can be read off.
That is the result of labelling the paths in the de Bruijn diagram by some boolean function of the neighborhood cells, such as repetition or shifting. When labelling is done according to evolution, the usual application of a de Bruijn diagram, the result leads to the Welch indices. In other words, if multiple continuations from a fixed node all lead to the same evolution, they define a compatible extension. This can be refined into a maximum compatible extension and so on, as spelled out both by Hedlund and by Nasu.
Hedlund's third great theorem relates the product LMR to the number of nodes
in the de Bruijn diagram, under conditions of surjectivity, but the same ideas
still have meaning for arbitrary automata. When the automaton is supposed to
have just two neighbors, and that number is prime, only one of the triple L,
M, R can differ from 1. If it is M, every configuration has M fully (that is,
-separated) distinct ancestors. If it is L or R, the automaton is of a
shifting type, but M may still exceed 1 if distinct ancestors nevertheless
coalesce when followed out to the extreme right or extreme left.
Suppose that 
is composite, for example 4 given a 
automatom.
Maybe then L=2, R=2, still leaving 
; such a possibility is included
in Eloranta's partial mermutivity, and one might even venture to say that is
the essence of the concept. Relative to the previous discussion, it would be
the equivalent of partial membranes, taking the form of moving kinks capable
of mutual annihilation or transformation; just the eventualities comprising
Eloranta's second paper.
To continue with the book reviews, the role of subshifts of finite type or of sofic systems and their relationship to cellular automata needs to be examined. The definitions are easy enough and it is not hard to guess their motivation. Once Hedlund's first great theorem is examined from the axiomatic topological viewpoint, continuous functions require sets of sequences derived from a countable list of exclusions. Such a list is readily obtained from the other characterization of continuous functions, as limits of shifts of extensions of block maps. In particular, it is the list of paths connecting the full set to the empty set in a subset diagram derived from the evolution-labelled de Bruijn diagram.
Independently of this, perhaps guided by another class of applications, someone decided to concentrate on finite lists of exclusions, generated with the help of an auxiliary matrix, the connection matrix for a distinctly-node- labelled graph. With an emphasis on endomorphisms and automorphisme as well as merely continuous functions, the natural consequence was to relate mappings between sets of sequences to mappings between their defining matrix, for which the principal source of information is the series of articles of R. F. Williams which have already been mentioned. Much of Williams' work concerns finding an axiomatic topological definition for shifts of finite type arising solely from the shift and intersection properties of the open sets of the topology.
Sofic systems met the objection that, in a theory of morphisms, subshifts of finite type were not closed. There was a fair amount of historical evolution and reassessment in their definition and interpretation, which in the end makes them depend on a dual of the kind of matrix which defines subshifts of finite type, and allows their characterization as the set of all (bi-infinite) paths through a labelled graph. This places the theory of sofic systems close to the theory of cellular automata; in effect we still need to relate the de Bruijn matrix of the cellular automaton to the path matrix of the shft of finite type whose homeomorphic image is the sofic system.
From the viewpoint of cellular automaton theory, we need to have a single matrix with nonnegative integer entries (preferably zeroes and ones) associated with each automaton, such that equivalence (properly defined) between matrices guarantees equivalence between configurations, and conversely. Until it is labelled by the evolution, there is only one de Bruijn diagram for each class (k,r) fo cellular automata, leaving its connection matrix inadequate to the purpose.
Labelling creates the de Bruijn fragments, say A and B for a binary automaton, but then there are two matrices, not one. There is also an entire family of moment matrices:
from which the first moment, the average number of
ancestors, may be obtained. For D itself, the number of
ancestors is constant and uniform, but products of A's
and B's occurring in the non-commutative binomial
expansion of 
tell how many ancestors each
configuration of length n has.
wherein 
is the tensor product is the second moment,
from which the variance may be derived. As with the first
moment, individual terms of 
describe corresponding
configurations, but unlike D, T can distinguish between
automata of the same Wolfram indices 
.
and so on.
The higher moments are required to fully distinguish automata, but if surjectivity is the only information required, it is already provided by T when the variance is zero, giving another criterion for surjectivity of automata.
Since T is the connection matrix of the pair diagram derived from the de Bruijn diagram, it can also be used to distinguish injectivity from the different degrees of surjectivity, although not necessarily by its eigenvalues alone. We should also bear in mind that Nasu's bundle mapping theorem based on Hedlund's third great theorem only directs us to some level of the subset diagram, not necessarily the second, and not necessarily the same for the left diagram as for the right diagram. If the corresponding matrix is chosen from the moment hierarchy, it should be a better representative of morphisms than any of the other matrices.
One thing which is easy enough to do is check whether the known symmetries preserve the moment matrices. Reflection transposes the de Bruijn matrix as well as its fragments, and transposition is respected by the tensor product. Simultaneous permutation of the arguments and values of the evolution function, that is, relabelling the states, is also a symmetry of the de Bruijn matrix, its fragments, and their tensor powers. That leaves the cluster-defining operation, permutation of the values alone, to be accounted for. But that merely permutes the summands in the sums of tensor powers, and so we find that all of the ordinary morphisms are spectrum-conserving operations on the moment matrices. For reflection, say, we are not saying that moment matrices are symmetric, only that we get equivalent matrices to go with equivalent configurations.
What should be seen as a much more interesting possibility is that there are
other equivalences, such as the one Voorehees uncovered as the background for
the Ito relations. This may not be too hard to prove algebraically, but in the
meantime it is possible to compare the eigenvalues of the T matrix for Ito
pairs. A spot check has not revealed any contradictions, although there is an
interesting contrast in the prototype 
pair in that the pair diagram
of Rule 18 has two connected components yet Rule 252 shows just one component.
Nasu's mapping theorem refers to just one of these components, but the T matrix involves both. The point needs further contemplation.