Melanie Mitchell
Paper #: 96-09-074
- Introduction Cellular automata (CAs) are decentralized, spatially extended systems consisting of large numbers of simple identical components with local connectivity. Such systems have the potential to perform complex computations with a high degree of efficiency and robustness, as well as to model the behavior of complex systems in nature. For these reasons CAs and related architectures have been studied extensively in the natural sciences, mathematics, and computer science. They have been used as models of physical and biological phenomena, such as fluid flow, galaxy formation, earthquakes, and biological pattern formation. They have been considered as mathematical objects about which formal properties can be proved. They have been used as parallel computing devices, both for the high-speed simulation of scientific models and for computational tasks such as image processing. In addition, CAs have been used as abstract models for studying emergent cooperative or collective behavior in complex systems. For collections of papers in all these areas, see, e.g., Burks (1970a); Fogelman-Soulie, Robert, and Tchuente (1987); Farmer, Toffoli, and Wolfram (1984); Forrest (1990); Gutowitz (1990); Jesshope, Jossifov, and Wilhelmi (1994); and Wolfram (1986). In this chapter I will review selected topics related to computation in CAs. The presentation will assume an elementary knowledge of the theory of computation, including formal-language theory and computability.