1. Introduction

The second law of thermodynamics implies that isolated microscopically reversible physical systems tend with time to states of maximal entropy and maximal ``disorder.'' However, ``dissipative'' systems involving microscopic irreversibility, or those open to interactions with their environment, may evolve from ``disordered'' to more ``ordered'' states. The states attained often exhibit a complicated structure. Examples are outlines of snowflakes, patterns of flow in turbulent fluids, and biological systems. The purpose of this paper is to begin the investigation of cellular automata (introduced in Sec. 2) as a class of mathematical models for such behavior. Cellular automata are sufficiently simple to allow detailed mathematical analysis, yet sufficiently complex to exhibit a wide variety of complicated phenomena. Cellular automata are also of sufficient generality to provide simple models for a very wide variety of physical, chemical, biological, and other systems. The ultimate goal is to abstract from a study of cellular automata general features of ``self-organizing'' behavior and perhaps to devise universal laws analogous to the laws of thermodynamics. This paper concentrates on the mathematical features of the simplest cellular automata, leaving for future study more complicated cellular automata and details of applications to specific systems. The paper is largely intended as an original contribution, rather than a review. It is presented in this journal in the hope that it may thereby reach a wider audience than would otherwise be possible. An outline of some of its results is given in Wolfram (1982a).

Investigations of simple ``self-organization'' phenomena in physical and chemical systems (Turing, 1952; Haken, 1975, 1978, 1979, 1981; Nicolis and Prigogine, 1977; Landauer, 1979; Prigogine, 1980; Nicolis et al., 1981) have often been based on the Boltzmann transport differential equations (e.g., Lifshitz and Pitaevskii, 1981) (or its analogs) for the time development of macroscopic quantities. The equations are obtained by averaging over an ensemble of microscopic states and assuming that successive collisions between molecules are statistically uncorrelated. For closed systems (with reversible or at least unitary microscopic interactions) the equations lead to Boltzmann's H theorem, which implies monotonic evolution towards the macroscopic state of maximum entropy. The equations also imply that weakly dissipative systems (such as fluids with small temperature gradients imposed) should tend to the unique condition of minimum entropy production. However, in strongly dissipative systems, several final states may be possible, corresponding to the various solutions of the polynomial equations obtained from the large time limit of the Boltzmann equations. Details or ``fluctuations'' in the initial state determine which of several possible final states are attained, just as in a system with multiple coexisting phases. Continuous changes in parameters such as external concentrations or temperature gradients may lead to discontinuous changes in the final states when the number of real roots in the polynomial equations changes, as described by catastrophe theory (Thom, 1975). In this way, ``structures'' with discrete boundaries may be formed from continuous models. However, such approaches become impractical for systems with very many degrees of freedom, and therefore cannot address the formation of genuinely complex structures.

More general investigations of self-organization and ``chaos'' in dynamical systems have typically used simple mathematical models. One approach (e.g., Ott, 1981) considers dissipative nonlinear differential equations (typically derived as idealizations of Navier-Stokes hydrodynamic equations). The time evolution given particular initial conditions is represented by a trajectory in the space of variables described by the differential equations. In the simplest cases (such as those typical for chemical concentrations described by the Boltzmann transport equations), all trajectories tend at large times to a small number of isolated limit points, or approach simple periodic limit cycle orbits. In other cases, the trajectories may instead concentrate on complicated and apparently chaotic surfaces (``strange attractors''). Nearly linear systems typically exhibit simple limit points or cycles. When nonlinearity is increased by variation of external parameters, the number of limit points or cycles may increase without bound, eventually building up a strange attractor (typically exhibiting a statistically self-similar structure in phase space). A simpler approach (e.g., Ott, 1981) involves discrete time steps, and considers the evolution of numbers on an interval of the real line under iterated mappings. As the nonlinearity is increased, greater numbers of limit points and cycles appear, followed by essentially chaotic behavior. Quantitative features of this approach to chaos are found to be universal to wide classes of mappings. Notice that for both differential equations and iterated mappings, initial conditions are specified by real numbers with a potentially infinite number of significant digits. Complicated or seemingly chaotic behavior is a reflection of sensitive dependence on high-order digits in the decimal expansions of the numbers.

Models based on cellular automata provide an alternative approach, involving discrete coordinates and variables as well as discrete time steps. They exhibit complicated behavior analogous to that found with differential equations or iterated mappings, but by virtue of their simpler construction are potentially amenable to a more detailed and complete analysis.

Section 2 of this paper defines and introduces cellular automata and describes the qualitative behavior of elementary cellular automata. Several phenomena characteristic of self-organization are found. Section 3 gives a quantitative statistical analysis of the states generated in the time evolution of cellular automata, revealing several quantitative universal features. Section 4 describes the global analysis of cellular automata and discusses the results in the context of dynamical systems theory and the formal theory of computation. Section 5 considers briefly extensions to more complicated cellular automata. Finally, Sec. 6 gives some tentative conclusions.

previous  l  next