|
Two-Dimensional Cellular Automata (1985) |
|
This paper has presented an exploratory study of two-dimensional cellular automata. Much remains to be done, but a few conclusions can already be given.
A first approach to the study of cellular automaton behavior is statistical: one considers the average properties of evolution from typical initial configurations. Statistical studies of one-dimensional cellular automata have suggested that four basic qualitative classes of behavior can be identified. This paper has given analogs of these classes in two-dimensional cellular automata. One expects that the qualitative classification will also apply in three- and higher-dimensional systems.
Entropies and Lyapunov exponents are statistical quantities that measure the information content and rate of information transmission in cellular automata. Their definitions for one-dimensional cellular automata are closest to those used in smooth dynamical systems. But rather direct generalizations can nevertheless be found for two- and higher-dimensional cellular automata.
Beyond statistical properties, one may consider geometrical aspects of patterns generated by cellular automaton evolution. Even though the basic construction of a cellular automaton is discrete, its ``macroscopic'' behavior at large times and on large spatial scales may be a close approximation to that of a continuous system. In particular domains of correlated sites may be formed, with boundaries that at a large scale seem to show continuous motions and deformations. While some such phenomena do occur in one dimension, they are most significant in two and higher dimensions. Often their motion appears to be determined by attributes such as curvature, that have no analog in one dimension.
The structures generated by two- and higher-dimensional cellular automata evolving from simple seeds show many geometrical phenomena. The most significant is probably the formation of dendritic patterns, characterized by noninteger growth dimensions.
Statistical measurements provide one method for comparing cellular automaton models with experimental data. Geometrical properties provide another. The geometry of patterns formed by cellular automata may be compared directly with the geometry of patterns generated by natural systems.
Topology is another aspect of cellular automaton patterns. When domains or regions containing many correlated sites exist, one may approximate them as continuous structures, and consider their topology. For example, domains produced by cellular automaton evolution may exhibit topological defects that are stable under the cellular automaton rule. In two-dimensional cellular automata, only point and line defects occur. But in three dimensions, knotted line defects (e.g., Ref. 42) and other complicated topological forms are possible. The topology of the structures supported by a cellular automaton rule may be compared directly with the topology of structures that arise in natural systems (cf. Ref. 43).
Geometry and topology provide essentially local descriptions of the behavior of cellular automata. Computation theory potentially provides a more global characterization. One may classify the behavior and properties of cellular automata in terms of the nature of the computations required to reproduce them. Even in one dimension, there are cellular automata that can perform arbitrary computations, so that at least some of their properties can be reproduced only by direct simulation or observation, and their limiting behavior is formally undecidable. The range of properties for which undecidability can occur is much larger in two dimensions than in one dimension. In particular, properties that involve a limit of infinite spatial size, even at finite times, can be undecidable. As higher-dimensional cellular automata are considered, the degree of undecidability that can be encountered in studies of particular properties increases.
