2. Outline

This special issue is a collection of papers on various aspects of cellular automata and their applications. Cellular automata have arisen in several disciplines; this collection represents an attempt to bring together the results, methods and applications of cellular automata from mathematics, physics, chemistry, biology and computer science.

Although the basic microscopic laws relevant to everyday natural phenomena appear to be known, no theoretical of complex natural phenomena. Even though the elementary components of a system may follow simple laws, the behaviour of the large collection of components which comprise the whole system may be very complex. Cellular automata provide examples in which the generation of complex behaviour by the cooperative effects of many simple components may be studied.

The laws of thermodynamics give a general description of the overall behaviour of systems governed by microscopically non-dissipative (reversible) laws. The second law of thermodynamics implies that such systems tend with time to disordered states of maximal entropy. In many systems, however, dissipation is important. In such cases, structure may arise spontaneously, even from a disordered initial state. The paper by Wolfram included below discusses the mathematical methods from dynamical systems theory. The paper identifies behaviour in cellular automata analogous to the limit points, limit cycles and chaotic ("strange") attractors found in studies of nonlinear ordinary differential equations. It suggests that these three classes of behaviour, together with a fourth class, cover the behaviour of all cellular automata. The identification of such universality in cellular automaton behaviour may represent a first step in the formulation of general laws for complex self-organizing systems analogous to the laws of thermodynamics.

Cellular automata in the fourth class identified by Wolfram are conjectured to be capable of "universal computation": with appropriate initial conditions, their behaviour may mimic the behaviour of any computer (and perhaps any physical system). This class of behaviour represents a higher level of complexity than has been found in continuous dynamical systems.

Self-organization in cellular automata occurs by the preferential generation of special sets of states with time; these preferred sets of states are known as "attractors" for the evolution. The paper by Waterman discusses the mathematical nature of the sets of states in cellular automata. The following paper by Lind uses ergodic theory to give a mathematical characterization of the states generated in two examples of cellular automata. The paper gives a calculation of the entropies which provide a statistical measure of the attractors for two examples of cellular automata. One of these calculations is made possible by a phenomenon described in the paper by Grassberger, where it is shown that for several simple cellular automata, time evolution according to one rule yields a subset of states with the special property that their evolution is governed by another rule. With time, evolution according to several rules is "attracted" to evolution according to a particular simple rule. Although not discussed in the paper, it seems possible that this phenomenon may serve as the basis for a renormalization group theory of cellular automata, in which the effective rules found at large times tend to fixed points in the space of all possible cellular automaton rules.

Cellular automata are usually assumed to be entirely deterministic. One may however introduce random noise directly into the cellular automaton rules, making cellular automata analogous to lattice spin systems at nonzero temperature. Such probabilistic cellular automata are found to exhibit phase transitions as a function of noise level. It is usually assumed that at each time step, the values of all the sites in a cellular automaton are updated together. The paper by Ingerson and Buvel discusses the phenomenology of cellular automata in which the site values are instead updated probabilistically, and asynchronously.

Whereas the first five papers consider the evolution of cellular automata from general initial configurations, the paper by Willson discusses some mathematical aspects of the growth of patterns by cellular automata from simple "seeds". The patterns obtained by evolution from simple initial states are generically found to be self-similar or "fractal" curves. The abundance of such curves in nature may well be a consequence of their generic formation by cellular automata.

One example of a two-dimensional cellular automaton which has received particular attention (see the bibliography) is the "Game of Life". This cellular automaton generates very complex structures, and has been shown to be capable of universal computation. The paper by Gosper presents an efficient algorithm for investigating the behaviour of the "Game of Life" (and other cellular automata with low dimensionality attractors). and gives as examples of its for use some very complex structures found in the "Game of Life".

The analogy on the one hand between cellular automata and physical systems, and on the other hand between cellular automata and digital computers suggests that cellular automata may provide a vehicle by which the methods and results of computation theory may be applied to physics, and vice versa. The paper by Margolus describes several advances in this direction. The cellular automata discussed in preceding papers are mostly dissipative or irreversible (a feature necessary for the formation of attractors). Margolus gives a simple construction for reversible or information-preserving cellular automata. In such cellular automata, it may be possible to use concepts such as energy, developed for the analysis of reversible physical systems. The paper then gives an example of a reversible cellular automaton capable of universal computation. The study of this and related cellular automata may provide a firm basis for relationships between physical and computational concepts.

Cellular automata may potentially be used as explicit models for a wide variety of physical systems. The paper by Vichniac explores some analogies between examples of two-dimensional cellular automata and various physical systems. The paper compares cellular automata with other discrete models of physical systems, particularly lattice spin models. The following paper by Toffoli considers the fundamental basis of cellular automaton models for physical systems, comparing their mathematical premises with those for differential equation models. The paper by Omohundro addresses the analogy between discrete cellular automation models, and continuous differential equation models, and gives a set of differential equations which reproduce the behaviour of a cellular automaton.

Cellular automata may also be used as models for biological systems. At a fundamental level, cellular automata may provide a mathematical basis in which to investigate the generation of the complex behaviour characteristic of living systems. The paper by Langton gives an explicit and comparatively simple example of a cellular automaton which exhibits self reproduction, a property often considered as a defining characteristic of living systems. This example, and similar investigations, may provide important insight into the logical or mathematical foundations of biological behaviour.

The following paper by Kauffman describes properties of random Boolean networks, and discusses their relevance to fundamental problems in biology. Each site in a random Boolean network has value 0 or 1, and evolves in discrete time steps according to definite rules which depend on the values of sites to which it is connected. Unlike in cellular automata, however, the sites to which a given site is connected are randomly chosen, rather than following a regular lattice. In addition, the rules which govern the evolution of site values are fixed for a given site, but may vary from one site to another. Random Boolean networks may be considered as direct models of highly interconnected systems such as neural networks, or as abstract models for complex systems of coupled nonlinear differential equations. Kauffman shows that certain classes of random Boolean networks universally evolve to generate definite structures. The generation and properties of these structures may have important consequences for biological and other systems, particularly in biological cell differentiation.

As a specific example of a biological system whose logical structure and function may be elucidated by cellular automaton models, Burks and Farmer discuss the structure and function of DNA sequences. They outline a novel approach to studies of DNA sequences, which begins not from the detailed chemical implementation of DNA, but rather from the overall logical purposes which the sequences achieve in the growth and evolution of biological organisms.

The following paper by Smith, Watt and Hameroff describes the application of cellular automata to explicit models of biological microtubule function. It is suggested that the cooperative action of many simple components in the cellular automaton model is responsible for the overall behaviour of microtubules.

Whereas the papers by Burks and Farmer and by Smith, Watt and Hameroff consider cellular automata as models of naturally-occurring complex chemical systems, the paper by Carter discusses the possibility that chemical systems could be specially constructed to implement cellular automaton computers at a molecular level. Site values would be represented by deformations in long linear molecules, and their time evolution rules implemented through interactions between neighbouring deformations. The computational components available at the molecular level are probably better suited to the construction of a computer based on cellular automata than on other models of computation, such as Turing machines. If such a computer could actually be constructed, its computational power is expected to be immensely greater than is possible with conventional macroscopic components.

Current investigations and applications of cellular automata rely on the implementation of cellular automata by conventional digital electronic computers. Toffoli describes a low-cost special purpose machine built with transistor-transistor logic (TTL) components which simulates two-dimensional cellular automata much faster than all but the largest general purpose computers.

Implementations of cellular automata with special-purpose electronics, or by microscopic physical systems, provide the "hardware" of cellular automaton computers. The application of such computers to real computational problems then requires the development of appropriate "firmware" and "software". The paper by Preston discusses the use of cellular automata for image processing, giving examples of cellular automaton rules which implement image processing functions. Several machines based on cellular automata have actually been constructed and used for biomedical image processing.

The paper by Hillis describes the Connection Machine, a rather general parallel processing computer based at a low level on cellular automata. Hillis discusses applications of the Connection Machine to problems in artificial intelligence research. A project to construct a Connection Machine with at least sites is currently underway.

The final paper by Crutchfield discusses the phenomenology and mathematics of the patterns generated through feedback by a video camera pointed at its own video monitor. This apparently simple system generates very complex patterns reminiscent of those obtained with cellular automata.

previous  l  next