Computation in Cellular Automata: A Selected Review

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 in 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 of 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.)