new books and old articles (12)

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:

D = A + B

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.




Harold V. McIntosh
E-mail:mcintosh@servidor.unam.mx