Date: Sat, 20 Apr 1996 21:04:23
To: ca@think.com
In Computational Analysis of One-Dimensional Cellular Automata just published by World Scientific, Burton Voorhees undertakes to "give an introduction to the analysis of cellular automata (CA) in terms of an approach in which CA rules are viewed as elements of a non-linear operator algebra, which can be expressed in component form much as ordinary vectors are in ordinary algebra."
This is a very distinct undertaking from trying to formulate the operations and concepts of cellular automata theory in terms of matrices insofar as possible, and also from the tradition in communication and coding theory to work with finite fields, recursion relations, and generating functions. Yet that approach is entirely consistent with with the book's emphasis on rules of evolution described by first degree polynomials while regarding other rules of evolution as perturbations on this basic theme.
The book contains many tables constructed in furtherance of these ideas, of which the ones associated with the sections concerning commutators deserve some attention. Relative to the background expressed in this review's preliminaries, commutators for binary automata are closely related to Williams' topological conjugacies. In other words, if X any Y are two rules of cellular automaton evolution, there may be a third rule T for which the composite two-generation rules XT and TY are the same. The relationship is more familiar when T is invertible; even so, there is always some degree of equivalence, even at the extreme where T is zero ("everything is equivalent, almost").
The historical precursor of this relationship is
Hiroyuki Ito,
"Intriguing Properties of Global Structure
in some Classes of Finite Cellular Automata,"
Physica D 31 318-338 (1988).
which worked out basins of attraction for the (2,1) Rule 18 (whose properties had been extensively investigated by Peter Grassberger) and the Rule 126 whose evolution is closely similar, just with thicker edges on all the triangles. The resemblance was stronger than that, plots of the distribution of cycle lengths, size of basins of attraction, and so on, coinciding almost exactly for the two rules.
Ito worked out a mapping from rule 18 to rule 126, and verified the resemblance between the rules by detailed alculations of their basins of attraction, which we might do nowadays with the "A and B matrices," or Voorhees' d0 and d1. Ito credits Grassberger with the reverse mapping, published in
P. Grassberger,
"New mechanism for deterministic diffusion,"
Physical Review A 28 3666-3667 (1983).
However, the book skips over a step in this saga, because it seems to have been Voorhees himself [bibliography 5] who noticed that Ito's coding from one rule to the next could be accomplished by a cellular automaton, whose rule was 252. Anyway, the idea was born that there were constellations of cellular automaton rules with related properties. Of course, that was based on empirical studies of a variety of automata as much as from any theoretical expectations, gaining strength as more and more theoretical underpinnings were discovered.
It is also true that it is possible to think about commutation amongst rules without connecting that with the commutative diagrams of category theory as Williams has done, but the ideas cannot be very far from one another. Another Voorhees article [bibliography 13, actually Complex Systems 7 309-326 (1993)] [to also complete bibliography 14: it is now Complex Systems 8 151-159 (1994)] refers to similar concepts circulating in Hedlund's circles, originating with
E. Coven, G. Hedlund and F. Rhodes,
"The commuting block maps problem,"
Transactions of the American Mathematical Society 249 113-138 (1979)
Here we have an interesting cycle, in which persons interested in mathematical communication theory and dynamical systems, thinking of composite mappings as cascaded shift registers, got interested in how their order of connection could affect the final result, taking up first degree mappings, at least with respect to an edge variable, as a case susceptible to analysis. Then the book's author, having developed a symbolism adapted for first degree mappings, comes along with a new interpretation [bibliography, 13]. Where will it all end? Not until Lagrange Interpolation Theory, expecially in finite fields, subsumes all these diverse mapping techniques into a single coherent approach, following which Hedlund's procedure is brought into play once again, this time for merely continuous mappings, not only the endomprphisms and automorphisms. And even then it probably won't be all over.
We say "constellations" to distinguish them from clusters as the latter appear in the Wuensche-Lesser Atlas or Hillman's determination of reversible automata, because they represent still larger groupings, something which is possible because they are not confined to surjective or injective mappings alone.
Empirical analyses of automata are replete with enumerations of restricted configurations which receive identical treatment with respect to two or more different automata. If any of those restrictions could be realized by defining classes of subshifts, they would thereby become susceptible to the theories of symbolic dynamics. In a case which will be discussed later on in more detail, Erica Jen has classified automata according to the size of the generators of the Garden of Eden - null, finite, countable, worse - which clearly relates the Subshifts of Finite Type to the second category.
In actually working with the concepts of Chapter 4, we see how careful and consistent one must be, between authors and (surprise!) with the same author. There are Wolfram rule numbers and Perry Rule numbers, reflecting two possible orderings of the digits in a number. Then, there is the question as to whether the automaton will be referred to by its christian name (and, or, xor) or its social security number (6, 12, 14). Once this has been straightened out, we can decide whether rules compose from the left (category diagrams) or the right (matrix products). A truly delightful experience awaits the unwary, or at least suffice it to say that lcau21 produces a composition table quite unlike the book's Table 4.3.
The reason for noticing this discrepancy results from trying to exploit the fact that Grassberger's Rule 18 is a composite of the (2,1/2) or and xor, and that many studies of its behavior depend on that fact. Rules 126 and 252 also factor, so it is tempting to pick up commuting triplets by associating terms in a composite (which is not necessarily the only way commutation can arise).
Generally speaking, textbooks which provide ample tables listing such items as composite rules and their factors, edge-insensitive, permutive, edge-linear, or other specialized automata, all serve to aid whomever is searching for patterns and relationships amongst automata. So we can only praise our author for the tabular information he has provided us. To balance the compliment with a quibble: "compliment" is when you say something nice to or about a person; "complement" is when you fill in the rest of the rule table, or finish some other undone task, or in electronics, invert the sign of the signal you're processing (Just as those who live in glass houses shouldn't throw stones, those who never learned touch typing shouldn't criticize authors' penmanship, but it's still a temptation).
To summarize today's discussion, chapter 4 describes idempotence, Ito's relationships, and existence (including symmetry properties) of constellations, something far greater than clusters, constructable using the author's generalization of Ito's, Grassberger's, and similar, observations. By their formulation, constellations tend to share invariants such as entropies (or whatever appropriate interpretation of the Perron eigenvalue) which in turn creates similarities in their patterns of evolution.