Date: Thu, 25 Apr 1996 23:53
To: ca@think.com
Substantially, our review of Burton Voorhees' new book, "Computational Analysis of One-Dimensional Cellular Automata" published by World Scientific in Singapore, with sales offices around the world, has been concluded. Amongst its other virtues, there are few other books primarily devoted to an exposition of the theory of cellular automata. Others have been conference proceedings, collections of articles, software or hardware manuals, and so on, and all have had their merits, but until now there has not been a textbook.
The author proposes it for a Junior level course; we had a discussion of this in our regular staff meeting a few days ago. For many years here in Puebla, there was a Sophomore course called Fortran III, dedicated to graphinf and graphics procedures that we used as a pretext to develop the theory of cellular automata (and the lcau programs). However, the students were never expected to do more than know some of the properties of cellular automata and prepare (or at least understand) the graphics displays. The following years there were courses on formal language theory and compiler construction in which things like regular expressions, finite automata, Chomsky's hierarchy, and the like were presented, giving an opportunity to look at cellular automata once again. Minsky's book, "Finite and Infinite Machines," or Aho and Ullman's dragon books were texts at this level.
In the meantime, we have a graduate level course on cellular automata theory in which all those things are supposed to be known, and the students have been told that they ought to procure Voorhees' book (as well as Wolfram's) and we feel that it will be just about right if they manage to master its contents.
Well, everyone will have their own environment and background from which to decide whether to use the book and at what level, so suffice it to say that it could be a textbook as well as a reference book.
As a reference work, both the author's own studies and Erica Jen's analyses occupy a good part of the volume, and invite attention for the details upon which they cast light as well as the opportunity they offer to generalize to other automata with diferent state sets and neighborhoods.
One example is the classification of automata according to the generators of the Garden of Eden, namely whether the number of poison words is zero, finite, linear, or (presumably) exponential relative to the length of the onfiguration. The first category corresponds to endomorphisms of the full shift, the second to the Subshifts of Finite Type, and the last two to Sofic Systems. As far as we know, this viewpoint relative to symbolic dynamics is not emphasized in the book nor elsewhere, although it is a logical extension of any study of Hedlund's point of view. If memory serves, the original motivation had to do with Feigenbaum's scaling theory, and involves still further considerations such as observing the rates of growth of those ancestors which actually exist when various kinds of boundary conditions are imposed.
When it comes to calculating ancestors, various techniques exist and have likewise had varying approaches and reasons for studying them. Regular Algebra offers some interesting symbolic calculations, not to mention the theory of factors and considerably more machinery. There are also numerical matrices, which form semigroups, with a whole well developed lore of semigroup theory waiting to be exploited. Voorhees has collected several semigroup tables, and has called attention to the possibility of having them further illuminate the properties of their cellular automata.
In practice, after getting considerable attention in the late fifties, including Samuel Eilenberg's treatises on monoids, semigroup theory has pretty much faded away from automata theory. To begin with, it is much more complicated than group theory, which in itself doesn't offer much engouragement to anyone who wants to evaluate long group products. But our recent reading of Hedlund suggests that there is much more to be gained by applying Welch's theory of indices, particularly when one wants to enumerate the reversible automata. Likewise Williams' theories of strong and weak equivalence, which has an impact on Voorhees' study of commutation and rule factorization, should open up a much greater range of equivalences for cellular automata .
At the time that inquiries were being made about the commutation of rules, there were also questions from other participants in the cellular automaton discussion group about whether it would be worthwhile to examine quadratic rules of evolution, considering the success which the study of linear (more properly, first degree) rules. This is another line of inquiry which has probably still not been exhausted. Voorhees was simply content to split rules into two parts, going on to concentrate on the linear part, although the splitting provides nice colorful diagrams. This is a subject which might bear reexamining, due consideration having been given to the new ideas which have been brought forward.
It remains to discuss the other new book, but to do this properly seems to be going to require some additional preparation. There is no question that it is an advanced research monograph, and although applications to cellular automata are promised in its promotional literature, there seems to be little doubt that the study of subshifts is an entire field whose central concern is different from cellular automata.
To the extent that they overlap, that is certainly well worth knowing about.