Date: Mon, 1 Apr 1996 22:13:09
To: ca@think.com
From time to time the question comes up, what is a good book to read on cellular automata? There aren't too many of them - Wolfram's World Scientific book (now reprinted), the proceedings of the 1989 CA conference, the manual for the CAM's, and maybe one or two others. Various suggestions are listed in the CA-Mail FAQ's.
Six weeks or so ago Burton Voorhees <burt@cs.athabascau.ca> announced:
> Subject: New CA Book From World Scientific > > Computational Analysis of One-Dimensional Cellular Automata > By Burton H. Voorhees > Recently published by World Scientific. ... > [that's ISBN 981-02-2221-1] > [... extract from the preface followed by the table of contents ...]
Those whose memory reaches a bit further back will recall that the book
Textile Systems for Endomprphisms and Automorphisms of the Shift By Masakazu Nasu Memoirs of the Americal Nathematical Society # 546 ISBN 0-8218-2606-9
was also suggested, on the level of "to be published" by an earlier correspondent. Both of these items are now available, and we are in the process of reading them, finally having bought copies. Of course, the two books are rather different, the latter being much more specialized.
Voorhees has summarized a considerable part of his own work during past years, placing emphasis on linear rules of evolution and the classification of one dimensional automata. But so also has Nasu, who has carried one- dimensional automata into two-dimensions, considering both the spatial shift operator and the temporal evolution by an automaton rule. Previous treatments of the Shift dynamical system have tended to concentrate on the shift operator alone.
Nevertheless, the reading of a book on cellular automata is not an activity to be undertaken lightly, the reason for this being that the subject is far more complicated than appears at first sight. These two books exemplify the confluence of two widely separated traditions; those currents have not at all developed in isolation from one another, but it would appear that the practitioners of the two specialties tend to have rather different skills and interests.
Cellular Automata seem to be an outgrowth of the theory of ordinary automata with roots in the work of von Neumann and his universal constructor, but drawing on the ideas of McCulloch and Pitts, the lore of language theory and especially regular expressions, and the emerging role of iteratitive arrays as electronic circuits became smaller and cheaper. If the invention of the Garden of Eden was not intended to refute universal construction, that was nevertheless the philosophical interpretation that arose for a time. Just a few words hardly do justice to a whole line of investigation, but it does not hurt to think of formal language theory, automated pattern recognition, the theory of relays, electrical circuits, and neurophysiology as topics which grew into a theory of automata.
Totally distinct from this were some of the ideas which Henri Poincare put forward to make some sense of the n-body problem, celestial mechanics, and the solution of differential equations in general. One of their consequences was the growth of the subject called Symbolic Dynamics, one of whose major proponents in the early part of the century was G.D. Birkhoff and some of his associates. Later on, G.A Hedlund devoted many, perhaps most, of his years to formalizing the topic, including the Americal Mathematical Society publication with that title.
As time went on, his approach became even more abstract, culminating in the document which is frequently cited in the cellular automaton literature, "Endomorphisms and Automorphisms of the Shift Dynamical System" published in Mathematical Systems Theory 4 320-375 (1969). Ten years in preparation according to the text, it is not an easy paper for non-specialists to read, placing it somethat on a par with von Neumann's "Foundations of Quantum Mechanics " in that regard.
Hedlund's manner of approach has much in common with communication theory in the tradition of Shannon, so its effects are rather noticeable in areas which have to do with cryptography and signalling, as well as the more traditional area of its origins, namely differential equation theory. Stephen Smale has been pretty much at the center of the latter, whereas the former apparently had its influence in such places as the Signal Corps laboratories at Fort Monmouth, some of whose employees seem to have eventually returned to Japan.
It might be an interesting project to try to untangle all the influences and cross influences, but for present purposes suffice it to say that cellular automata and symbolic dynamics were evolved by workers who were substantially unaware of each other. The discomfiture of Lewis Carrol's intrepid band of snark hunters seems to have been matched in recent times by whomever has tried to come to grips with Curtis, Hedlund, and Lyndon's Theorem 3.4.
Whereas Hedlund seems to have been content to topologize sequence space in order to describe its continuous functions and their ramifications, others seem to have wanted concrete examples, leading to the concept of Shifts of Finite type, a line pursued by William Parry from the University of Warwick, and its elaboration into Sofic Systems, by Benjamin Weiss and others. Most of this work is an inextricable mixture of topology, measure theory, and just plain combinatorics. Yet those who work with cellular automata theory see it as little more than the theory of "all paths through a maze" based on hardly more than the theory of regular expressions, if you will.
Here, a central reference is Masakazu Nasu's "Local Maps Inducing Surjective Global Maps of One-Dimensional Tessellation Automata" which also appeared in Mathematical Systems Theory, 11 327-351 (1978). While referring constantly to Hedlund, the exposition is nevertheless based on graphs; concretely, the de Bruijn diagram, the subset diagram, and the "vector subset diagram" which seems to bear on the subset diagram in much the same way that sofic systems relate to shifts of finite type.
Although our intention here is to review these two new books, the foregoing commentary should emphasize our conviction that creating a sufficiently detailled analysis practically requires going back and reconstructing automata theory from the ground up, bearing in mind that whatever merit is to be found in the topological and measure theoretic versions, the situation is analogous to the plight of a little girl in a family I once knew where English, German and Italian were spoken with equal fluency: "Dear, Please DON'T mix your languages!"
For next time, the topic will be a survey of Hedlund's article, the one referenced above.