Edited by David Griffeath and Cristopher Moore

This book not only discusses cellular automata (CA) as accoutrements for simulation, but also the actual building of devices within cellular automata. CA are widely used tools for simulation in physics, ecology, mathematics, and other fields. But they are also digital "toy universes" worthy of study in their own right, with their own laws of physics and behavior. In studying CA for their own sake, we must look at constructive methods, that is, the practice of actually building devices in a given CA that store and process information, replicate and propagate themselves, and interact with other devices in complex ways. By building such machines, we learn what the CA's dynamics are capable of, and build an intuition about how to "engineer" the machine we want. We can also address fundamental questions, such as whether universal computation or even "living" things that reproduce and evolve can exist in the CA's digital world, and perhaps, how these things came to be in our own universe.

About the Editors

David Griffeath is a Professor of Mathematics at the University of Wisconsin Madison. He received his Ph.D. in Mathematics from Cornell University in 1976. His research combines mathematical analysis and computer visualization in the study of complex spatial systems. Over the past decade his investigations have focused on deterministic and random cellular automata as prototypes for self-organizing phenomena such as spiral formation in excitable media, the shapes of growing crystals, and the emergence of traffic jams. A popular account of much of this work may be found at his award-winning web site, the Primordial Soup Kitchen. Griffeath is also a member of the External Faculty of the Santa Fe Institute.

Cris Moore received his Ph.D. in Physics from Cornell University in 1991, where he showed that questions about the long-term behavior of simple two-dimensional dynamical systems can be undecidable. Since then he has published numerous papers on physics and computation, including quantum computation, analog computation, computational complexity in statistical physics, phase transitions in NP-complete problems, and cellular automata. He has also contributed to the theory of tilings, combinatorial games, parallel circuits, and computation over quasigroups and monoids. He now holds a joint appointment in the Computer Science Department and the Department of Physics and Astronomy at the University of New Mexico. He is also a member of the External Faculty of the Santa Fe Institute.