Date: Mon, 22 Apr 1996 23:33:17
To: ca@think.com
Someone looking for a textbook on cellular automata theory, which treats the theory on its own merits wherein the underlying lattice is a fundamental part of the topic rather than appendage to the theory of finite automata, would do well to consider Burton Voorhees' "Computational Analysis of One-Dimensional Cellular Automata" which we have been discussing. As his preface says, "The actual mathematics used is not hard, and the material should be available to anyone with a junior level university background, and a certain degree of mathematical maturity." Matrices are for multiplying but not diagonalizing, the only finite field is a boolean algebra and the algebra never mentions Galois theory explicitly, but there IS a contour integral in theorem 5.13.
Text book or not, it is one of the few places where the "advanced" theory of cellular automata may be found, meaning the use of the de Bruijn diagram for deriving properties of automata, concern with ancestors, the Garden of Eden, surjectivity and injectivity, and all those aspects which go beyond the mere phenomonology of observing evolution and compiling statistics about it. Aside from the one chapter on time series and some discussion of entropy, the book makes no attempt to relate automata theory to statistical mechanics, which is a whole field for investigation in its own right.
On the other hand, it strongly reflects the research interests of its author, which accounts for a concentration on binary, first neighbor, automata; the same ones Stephen Wolfram studied so intensively (and let us not lose sight of the fact that Wolfram was one of the first to observe ALL the automata of a given class rather than just the one which served the moment's purpose). Additionally, the book gravitates around linear automata, those whose rule of evolution can be expressed via a multinomial of the first degree in variables representing the cells of the neighborhood.
Within these margins the book contains a wealth of techniques, procedures, and collected data, this latter dispersed in tables throughout the text and six additional appendices. Between most chapters there are collections of color plates embodying several of the author's techniques for visualizing the properties of automata; it is all quite colorful, and even possessed of a certain abstract beauty.
The reason authors, including Guan and He, or Martin, Odlyzko and Wolfram, amongst many others, have chosen to work with additive rules, was undoubtedly the perception that such rules would be susceptible to mathematical analysis while other rules might not be so easily treated. Nor is there much doubt that they actually obtained a large collection of results; if formulas for periods, transient lengths, sizes of basins of attraction, did not yield nice algebraic formulas, they did give closed expressions in terms of Euler's phi function, the Moebius inversion formula, or what not. Nice number theoretical results.
Unfortunately all of this activity has taken place against a background which has been better understood by some persons than by others, apparently without there having any single comprehensive picture. Even now, we can wonder whether it will be necessary to bring differential algebra (or finite difference algebra) in the style of Ritt and Kolchin into the picture, but the large body of knowledge implied by the work of Hedlund and his successors was not widely disseminated amongst automata theorists, and even those who were aware of the work may not have been fully aware of its implications.
Speaking more personally, it is only lately that we can even claim to be able to read Hedlund's articles, and that only as a result of longtime efforts and a more intensive seminar lasting months. Obviously others have had advance warning or better preparation, but there is evidence that even those concepts which have reached across from one field to another have been as fully appreciated as they might have been. Two or three years ago, when the cellular automaton discussion group was approached by Prof. Voorhees seeking information about the commutativity of cellular automaton rules, did anyone suspect the relation to Williams' equivalences, or even think to cite Rhodes' paper? We might have saved him a bit of trouble if we'd have known these things.
Well, to flog a dead horse just a little bit more, there is still this question
about the number of counterimages of a surjective cellular automaton map. There
are several answers, depending upon the level at which they are asked. At the
local mapping level, there are always 
, for k states an neighborhood
content n. Mirroring this result in de Bruijn fragments is another story, but
the result is clear and definitive enough.
An immediate complication is the fact that the counterimages need not have the same period as their sequences, although there are limits and divisibility relationships. Therefore it one works with basins of attraction for periodic automata the fact that these larger counterimages exist may go unnoticed; the proper interpretation of a Garden-of-Eden result for such automata should take this into account, just as it should note that there is only a finite number of the wider counterimages.
Another complication lies in the transition from local mapping to global mapping, especially as it is influenced by a topology in which locally distinct counterimages coalesce in the limit. At least one will survive, maybe more, and possibly all. This is governed by Hedlund's third great theorem and the Welch indices. Of these, the left and right indices behave sedately and multiply under composition. If left and right subset diagrams are constructed, the indices identify the strata on which the ergodic set of the subset diagram is to be found. Nasu's theorem, an interpretation of Hedlund's result, assures this.
If the automaton is not surjective, the ergodic set permeates the subset diagram, without necessarily encompassing all of it. The transients are also important and interesting. Even though Welch's indices describe the ergodic stratum, the acute observer will notice that Nasu's theorem describes an inequality, and that the statement of Hedlund's theorem has a proviso (as it turns out, resulting from and amply justifying all the preliminary attention to degrees of periodicity, recurrence, and so on).
For observing these details, it is useful to work with something more elaborate
than Wolfram's (or Voorhees's) (2,1) automata; the Amoroso-Patt example with
automata gives the smallest binary instance, although there are some
nice examples using 
automata.
Consider the 
automaton 14433, whose rule table is
which is quiescent in all three states, but for which 1* has (02)* and (20)* as counterimages also. The de Bruijn fragments are row stochastic, so Welch's R index is 1. The reflected automaton follows rule 18369, whose subset diagram reveals that L is 3, a level to which the maximum compatible extensions arrive in two steps, with some dithering. This is also consistent with the two trees of height 2 rooted on states 0 and 2.
Were L M R = 3, we would conclude that M = 1; but by Nasu's theorem that is only a lower bound for the multiplicity.
If we now go on to construct the pair diagram and the triple diagram, we find some interesting features. The triple diagram exhibits exactly one loop, which means that the quiescent 1 background has three ancestors, and that it is the only such configuration, which is hardly uniform multiplicity.
In the pair diagram, there is a subdiagram containing internal loops, from
which the diagonal has only incoming links. That means that there are some
configurations (but not all) which have two ancestors, but there are crucial
junctures following which both ancestors must coincide and continue to
coindide thereafter, while running onwards to the right. That means that
there are many configurations with two distinct 
-separated (according
to Hedlund) ancestors, and still others agreeing to the rightwards of some
juncture.
If we ask what our dynamical systems theorests have to say about this, we will find the concepts of mergibility and definiteness.
With respect to the pair diagram, mergible means that the diagonal has no exits to loops. Thus any sufficiently long path (pair of paths in the de Bruijn diagram) has to have originated within the diagonal; the minimul such length is an index of mergibility. Alternatively, running in the other direction, long enough forces the beginning into the diagonal.
Definitiveness is a closely related concept; it says that there have been no entrances into the diagonal from loops. Thus (unless there are some completely exterior loops) any sufficiently long path in the pair diagram has to enter the diagonal; a similar definition embodies the other handedness.
Definiteness allows loops in the pair diagram which do not intersect the
diagonal; this is where totally 
-separated, bilaterally transitive,
and such adjectives enter Hedlund's and Nasu's theorems. Injectivity says
NO loops outside the diagonal, intersecting or not, which serves to fix the
multiplicity M; from there on there should be no difficulty in applying
Hedlund's third great theorem. Note that other authors sometimes use the
adjectives "separating" and "closing."
In conclusion, surjectivity admits a variety of multiplicities running from injectivity to a full complement of counterimages, all with a wide variety of intermediates.
In summary, we have given a variety of arguments favoring the book under review, pointing out that there are few others treating cellular automata at a comparable theoretical leval. At the same time, it can hardly be overstated, that so far there has lacked a really elegant overview of cellular automata theory; for some years this placed it on the videogame level, where the attitude was "look at this nice fractal pattern I've just now generated!" But we also tend to get lost on another level, where there are elaborate formulas and theories to list the nice fractals, but the feeling of much computation (or theorem proving) for little practical gain, or understanding, remains.
Still, the book is a worthwhile contribution to furthering this understanding and we appreciate the sentiment involved with "My hope is that in describing the little that I have been able to see, it will encourage others to go further." Maybe that rascal in the front row; maybe the author himself; let us wait and see.