[This review was jointly written with Cris Moore, and appeared in the Bulletin of the London Mathematical Society, vol. 35, no. 2 (March 2003), pp. 282--284. I have added a few links. --- CRS]
Cellular automata (CAs) are discrete spatially extended dynamical systems, capable of a vast variety of behaviors. Some people study them for their own sake; some use them to model real phenomena; and some speculate that they underlie fundamental physics. The present volume is the most comprehensive single-author book on CAs to date, and provides a useful unified reference to many ideas scattered through the literature. While aimed at an audience of physicists, it should be useful and comprehensible to mathematicians and computer scientists. While no one book could exhaust such a wide subject, there are several places where this one falls short, and others where it is too generous to ideas that, while popular ten years ago in the complex systems community, have not borne fruit.
After an introduction and a lengthy chapter on formalism (mostly discrete mathematics), the author begins with a phenomenological exploration of basic CA rules. He discusses periodic domains and particles, temporal and spatial correlations, mean-field theory, and Wolfram's grouping of CAs into four rather ill-defined classes. He then discusses Langton's lambda parameter and the ``edge of chaos'' idea. Unfortunately, he repeats early claims that CAs must evolve towards the edge of chaos in order to perform computational tasks, even though this was thoroughly demolished by Mitchell, Hraber and Crutchfield in 1993.
After a nice discussion of Conway's game of life and a sketch of the proof that it can perform universal computation, in Chapter 4 the author gives an introduction to the theory of continuous dynamical systems, and how notions like invariant measure carry over into CAs. Chapter 5 mainly enumerates periodic orbits and bounds transient times.
Chapter 6 gives an introduction to the theory of languages and automata, including non-regular languages. It focuses, however, on the dynamics of the regular languages generated by CAs. That CAs can give rise to context-free and context-sensitive languages is reduced to a brief mention of the work of Hurd. Also, the author misses all of the recent work of Machta et al. on the computational complexity of simulating CAs and physical systems, and their relationship to parallel circuit complexity.
Chapter 7 discusses probabilistic CAs and gives an introduction to scaling, phase transitions, and the Ising model of magnetism. It also explains why naive CA simulations often produce unphysical results, and how Creutz and others have designed CA rules that avoid this. It does not explain why most computational physicists still prefer traditional Monte Carlo simulations to CAs.
Chapter 8 has some excellent material on reversible CAs, and on work by Margolus, Takesue, Pomeau, Goles and Vichniac on building thermodynamics from microscopically reversible dynamics. After discussing coupled map lattices and spatio-temporal intermittency, the chapter concludes with a smorgasbord of popular complex systems, including Kauffman's Boolean Nk networks, random maps, and sandpiles. There is a brief section on reaction-diffusion systems, which is the only place in the book where CAs appear as models of pattern formation. (The section on quantum CAs, unfortunately, ignores work by Meyer, Watrous and others.) The chapter presents a CA model of AIDS and immune response, but is far too uncritical about whether such crude models tell us anything important about AIDS.
Chapter 9 gives a good introduction to lattice gases, discussing why CAs can, sometimes, efficiently simulate hydrodynamics and its generalizations. In general, fluid motion in a lattice gas inherits the unphysical anisotropy of the lattice. If the lattice has the right symmetry properties, however, isotropy reappears on large scales. The author's orientation towards physics comes through clearly here, since he does not explain hydrodynamic notation (for example, \Nabla \cdot v) at all.
Chapter 10, on neural networks, has nothing to do with the rest of the book.
Chapter 11 focuses on ``artificial life,'' including agent-based models, von Neumann's and Langton's self-reproducing automata, and genetic algorithms. It presents the author's detailed model of land combat. This certainly has interesting dynamics, but we are left to wonder whether it is at all realistic.
Chapter 12 asks ``Is Nature, underneath it all, a CA?'' Many have speculated that the world's apparent continuity masks a fundamentally discrete physics, among them Richard Feynman, John Wheeler and T. D. Lee. (In a sense, students of topological quantum field theories are pursuing this idea.) CAs are possible candidates for such a physics, and Fredkin, Toffoli, Margolus and Wolfram have advocated this vigorously. Many subtle issues are involved: for instance, to capture general relativity's coupling between matter and space-time curvature, the values of the cells must modify the lattice structure. Unfortunately, this chapter is simply a potpourri of speculative theories, without any exploration of whether these have led to any progress in physics. The author is entitled to philosophize, but not to indiscriminately mix field theory, mystical triads, quantum computation and Fritjof Capra. It would have been far better to work through a few models with detail and rigor, and let readers judge their worth.
The book ends with two appendices, one describing currently available CA hardware and software, and the other listing web pages related to CAs. The bibliography is extensive, although far from complete.
Overall, the author's choice of topics is suboptimal: some are out of date, some are extraneous, some deserve a more critical examination, and some are conspicuous by their absence. Nonetheless, there is much useful material here, and we are not aware of anything better with a comparable scope. CA enthusiasts will want copies on their shelves.
Artificial Life / Cellular Automata / Computers and Computing / Hydrodynamics / Physics / Self-Organization, Complexity, etc.
Currently in print as a hardback, ISBN 981-02-4623-4, US$112, and as a paperback, and as a paperback, 981-238-183-X, US$58 (if ordered directly from the publisher)