Date: Wed, 17 Apr 1996 22:33:55
To: ca@think.com
Of the two books, Voorhees' Computational Analysis of One-Dimensional Cellular Automata by World Scientific would be more suitable as a textbook, while Nasu's Textile Systems for Endomprphisms and Automorphisms of the Shift from the American Mathematical Society is essentially an advanced research monograph. Both are neatly prepared, apparently from TeX prepared by the author in Nasu's case, and something akin to ChiWriter for Voorhees' book. In either case, the mathematical text seems to have been meticulously prepared, yet both contain one or two idiosyncracies which either referees or some copy editor ought to have detected: Nasu's use of "weaved" where "woven" would probably be more gramatically correct, and Voorhees' pluralization of -x words using -icies. If there are ever second printings, electronic correction of these anomalies should be a triviality.
As described in its announcement, Voorhees' book has twelve chapters, six appendices, and a bibliography (of 89 items), all for a total of 275 pages. Part of the introduction is a bibliography of fourteen of the author's own papers, whose subject matter is consistent with the book's emphasis on one- dimensional automata of Wolfram's type type (2,1), and with additive rules at that. This is a realm for which reasonably explicit calculations are possible, from which concrete results can be used to treat the topics of the last chapters, wherein surjectivity, injectivity, and the calculation of ancestors are considered.
There are many diagrams, illustrations, and tables, including the compilation of results in the appendices. In keeping with its possible use as a textbook, each chapter has a handful (that is, ten or so) of exercises. The book breaks down more or less according to the following lines:
One of the author's specialties has been to work with a sort of algebra of automaton rules, which is part of more extensive efforts to deduce family relationships amongst automata. This algebra foresees giving additive (and linear homogeneous) rules a privleged position amongst all rules, in no small part due to an intention to use linear algebra over finite fields or else integers modulo n to study their evolution.
Family relationships include factoring rules, enbedding them in larger neighborhoods, and restricting the neighborhood. The rule algebra of chapter 2 has the defining of rule commutativity as one of its goals, something which is also one of the author's specialties, explained at greater length in chapter 4, and which probably has additional relevant interpretation in terms of William's commutative diagrams.
The study of fixed points and cycles comprising the third chapter has an elegant formulation in terms of de Bruijn diagrams, something about which Erica Jen was amongst the first to publish. In fact there is much reference to her detailed classification of (2,1/2) and (2,1) automata, much of it in terms of recursion relations and number theory.
Chapter 5 introduces a technique for visualizing the additivity, or lack thereof, as introduced in Chapter 2. It produces something similar to the plaid diagram, but it displays, for the one-sided shift, whether or not configurations i and j obey f(i+j) = f(i) + f(j). Since this all depends upon whether neighborhoods themselves obey this property, the result is a nice fractal picture, in the topology of the shift. For the (2,1) automata, fifteen color plates (the other one is identically zero) illustrate nontrivial "obstruction classes;" the ways in which rules depart from additivity.
Periodic additive rules admit matrix representation for the evolution of rings of cells; typically by circulant matrices whose eigenvalues are described by Tchebycheff polynomials and whose eigenvectors form discrete Fourier transform matrices, although the results eventually need to be referred to a finite field. The author and others have made such analyses. Whether or not the rules are injective is always interesting, to which Hedlund's third great theorem concerning the Welch indices, is relevant. Although periodic configurations have periodic ancestors, those periods do not always coincide.
Running forward in time lends interest to knowing the onset of periodicity, the height, leafiness, and convergence ratios of the tree of evolution, its description by such measures as entropy, and related data. It is no less interesting to run backward in time, obtaining the same information in terms of ancestors. In the process Langton's parameter lambda is encountered, not to mention all of the interesting results in Wuensche and Lesser's Atlas.
For linear rules, the same opportunity exists to use linear algebra, recursion relations, and finite field theory to calculate ancestors that was used for the calculation of evolution. Additionally, the subset diagram and symbolic de Bruijn matrices can be used.
Chapter 8 is dedicated to the bellwether of all additive binary rules, the exclusive or.
Sometimes uniform stretches lose out, yielding their popularity to configurations of simple periood, such as alternating zeroes and ones. There is a community of rules for which simple periodicity dominates, but there are still minorities of rules in which the dominance passes to longer periods with more complicated unit cells. Finally there is a realm in which absolute democracy, in the form of Hedlund's second great theorem, the one about uniform multiplicity, prevails.
Chapter 9 introduces another specialty of the author's, which he calls the basic matrix. Instead of creating the connectivity matrix of the de Bruijn diagram by placing a 1 where the partial neighborhoods can overlap, or of creating a symbolic matrix by placing the image cell at that location instead of a 1, this time the links tell whether there exists a neighborhood of double length, which starts with the row index, but which evolves into the column index.
Trying to multiply such matrices would imply a tower of neighborhoods such that paths in the connection matrix would describe consecutive initial segments of the members of the tower, as successive generations evolve. But this is not the use to which these matrices are put; rather longer and longer segments are followed through a single generation, yielding a sequence of matrices with fractal structure, supposing that indices are mapped into "decimals" the same way they were in earlier chapters. Samples for fifteen different (2,1) rules are shown with the help of another collection of color plates.
Quite a few questions can be asked about the Garden of Eden. One arises from relating periodic configurations to arbitrary configurations, even without going into all the periodicity refinements which characterize symbolic dynamics. The simplest complication arises when a counterimage has a longer period than that of the lattice of the configuration. When rules aren't surjective, there is still characterizing growth rates, and growth rates subject to a variety of constraints.
Another possible question is: what are the rules exhibiting prescribed "poison words" or groups of poison words. This is like characterizing subshifts, and is altogether complicated by the fact that it is hard to create a subset diagram to order, in the way that it can be done for boolean properties of the de Bruijn diagram.
Chapter 11 ventures into the arena of time sequences for an automaton, as distinguished from spatial distributions. Interesting results exist.
The book concludes with a discussion of surjectivity, to be found in Chapter 12, a topic of interest for discovering reversible cellular automata; particularly so when the rules of evolution are algebraic conditions for their solubility can be discussed algebraically, especially for linear and linear inhomogeneous rules.
Reference is made to the original determination of Amoroso and Patt, to Hedlund's theorems, and to the de Bruijn and Subset diagrams. Some interesting diagrams are shown which could be used to calculate the products of symbolic de Bruijn diagrams, the ones which originate from the "vector subset diagram."