1. Introduction

Cellular automata are mathematical models for systems in which many simple components act together to produce complicated patterns of behavior. One-dimensional cellular automata have now been investigated in several ways (Ref. 1 and references therein). This paper presents an exploratory study of two-dimensional cellular automata. (1) The extension to two dimensions is significant for comparisons with many experimental results on pattern formation in physical systems. Immediate applications include dendritic crystal growth, reaction-diffusion systems, and turbulent flow patterns. (The Navier--Stokes equations for fluid flow appear to admit turbulent solutions only in two or more dimensions.)

[ Figure 1 ] Neighborhood structures considered for two-dimensional cellular automata. In the cellular automaton evolution, the value of the center cell is updated according to a rule that depends on the values of the shaded cells. Cellular automata with neighborhood (a) are termed ``five-neighbor square''; those with neighborhood (b) are termed ``nine-neighbor square.'' (These neighborhoods are sometimes referred to as the von Neumann and Moore neighborhoods, respectively.) Totalistic cellular automaton rules take the value of the center site to depend only on the sum of the values of the sites in the neighborhood. With outer totalistic rules, sites are updated according to their previous values, and the sum of the values of the other sites in the neighborhood. Triangular and hexagonal lattices are also possible, but are not used in the examples given here. Notice that five-neighbor square, triangular, and hexagonal cellular automaton rules may all be considered as special cases of general nine-neighbor square rules.

A cellular automaton consists of a regular lattice of sites. Each site takes on possible values, and is updated in discrete time steps according to a rule that depends on the value of sites in some neighborhood around it. The value of a site at position in a one-dimensional cellular automata with a rule that depends only on nearest neighbors thus evolves according to

There are several possible lattices and neighborhood structures for two-dimensional cellular automata. This paper considers primarily square lattices, with the two neighborhood structures illustrated in Fig. 1. A five-neighbor square cellular automaton then evolves in analogy with Eq. (1.1) according to

Here we often consider the special class of totalistic rules, in which the value of a site depends only on the sum of the values in the neighborhood:

These rules are conveniently specified by a code

We also consider outer totalistic rules, in which the value of a site depends separately on the sum of the values of sites in a neighborhood, and on the value of the site itself:

Such rules are specified by a code

This paper considers two-dimensional cellular automata with values or at each site, corresponding to . Table 1 gives the number of possible rules of various kinds for such cellular automata. A notorious example of an outer totalistic nine-neighbor square cellular automaton is the ``Game of Life,'' with a rule specified by code .

[ Table 1 ] Numbers of possible rules of various kinds for cellular automata with two states per site, and neighborhoods of the form shown in Fig. 1. The two entries for reflectional symmetries of the hexagonal lattice refer to reflections across a cell and across a boundary, respectively. The number of quiescent rules (defined to leave the null configuration invariant) is always half the total number of rules of a given kind.

Despite the simplicity of their construction, cellular automata are found to be capable of very complicated behavior. Direct mathematical analysis is in general of little utility in elucidating their properties. One must at first resort to empirical means. This paper is a phenomenological study of typical two-dimensional cellular automata. Its approach is largely experimental in character: cellular automaton rules are selected and their evolution from various initial states is traced by direct simulation. (2) The emphasis is on generic properties. Typical initial states are chosen. Except for some restricted kinds of rules, Table 1 shows that the number of possible cellular automaton rules is far too great for each to be investigated explicitly. For the most part one must resort to random sampling, with the expectation that the rules so selected are typical. The phenomena identified by this experimental approach may then be investigated in detail using analytical approximations, and by conventional mathematical means. Generic properties are significant because they are independent of precise details of cellular automaton construction, and may be expected to be universal to a wide class of systems, including those that occur in nature.

Empirical studies strongly suggest that the qualitative properties of one-dimensional cellular automata are largely independent of such features of their construction as the number of possible values for each site, and the size of the neighborhood. Four qualitative classes of behavior have been identified in one-dimensional cellular automata. Starting from typical initial configurations, class-1 cellular automata evolve to homogeneous final states. Class-2 cellular automata yield separated periodic structures. Class-3 cellular automata exhibit chaotic behavior, and yield aperiodic patterns. Small changes in initial states usually lead to linearly increasing regions of change. Class-4 cellular automata exhibit complicated localized and propagating structures. Cellular automata may be considered as information-processing systems, their evolution performing some computation on the sequence of site values given as the initial state. It is conjectured that class-4 cellular automata are generically capable of universal computation, so that they can implement arbitrary information-processing procedures.

Dynamical systems theory methods may be used to investigate the global properties of cellular automata. One considers the set of configurations generated after some time from any possible initial configuration. Most cellular automaton mappings are irreversible (and not surjective), so that the set of configurations generated contracts with time. Class-1 cellular automata evolve from almost all initial states to a unique final state, analogous to a fixed point. Class-2 cellular automata evolve to collections of periodic structures, analogous to limit cycles. The contraction of the set of configurations generated by a cellular automaton is reflected in a decrease in its entropy or dimension. Starting from all possible initial configurations (corresponding to a set defined to have dimension one), class-3 cellular automata yield sets of configurations with smaller, but positive, dimensions. These sets are directly analogous to the chaotic (or ``strange'') attractors found in some continuous dynamical systems (e.g., Ref. 10).

Entropy or dimension gives only a coarse characterization of sets of cellular automaton configurations. Formal language theory (e.g., Ref. 11) provides a more complete and detailed characterization. Configurations may be considered as words in a formal language; sets of configurations are specified by the grammatical rules of the language. The set of configurations generated after any finite number of time steps in the evolution of a one-dimensional cellular automaton can be shown to form a regular language: the possible configurations thus correspond to possible paths through a finite graph. For most class-3 and -4 cellular automata, the complexity of this graph grows rapidly with time, so that the limit set is presumably not a regular language (cf. Ref. 13).

This paper reports evidence that certain global properties of two-dimensional cellular automata are very similar to those of one-dimensional cellular automata. Many of the local phenomena found in two-dimensional cellular automata also have analogs in one dimension. However, there are a variety of phenomena that depend on the geometry of the two-dimensional lattice. Many of these phenomena involve complicated boundaries and interfaces, which have no direct analog in one dimension.

Section 2 discusses the evolution of two-dimensional cellular automata from simple ``seeds,'' consisting of a few nonzero initial sites. Just as in one dimension, some cellular automata give regular and self-similar patterns; others yield complicated and apparently random patterns. A new feature in two dimensions is the generation of patterns with dendritic boundaries, much as observed in many natural systems. Most two-dimensional patterns generated by cellular automaton growth have a polytopic boundary that reflects the structure of the neighborhood in the cellular automaton rule (cf. Ref. 14). Some rules, however, yield slowly growing patterns that tend to a circular shape independent of the underlying cellular automaton lattice.

Section 3 considers evolution from typical disordered initial states. Some cellular automata evolve to stationary structures analogous to crystalline forms. The boundaries between domains of different phases may behave as if they carry a surface tension: positive surface tensions lead to large smooth-walled domains; negative surface tensions give rise to labyrinthine structures with highly convoluted walls. Other cellular automata yield chaotic, class-3, behavior. Small changes in their initial configurations lead to linearly increasing regions of change, usually circular or at least rounded.

Section 4 discusses some quantitative characterizations of the global properties of two-dimensional cellular automata. Many definitions are carried through directly from one dimension, but some results are rather different. In particular, the sets of configurations that can be generated after a finite number of time steps of cellular automaton evolution are no longer described by regular languages, and may in fact be nonrecursive. As a consequence, several global properties that are decidable for one-dimensional cellular automata become undecidable in two dimensions (cf. Ref. 15).

previous  l  next