Cellular Automata

by Stephen Wolfram

T

appears that the basic laws of physics relevant to everyday phenomena are now known. Yet there are many everyday natural systems whose complex structure and behavior have so far defied even qualitative analysis. For example, the laws that govern the freezing of water and the conduction of heat have long been known, but analyzing their consequences for the intricate patterns of snowflake growth has not yet been possible. While many complex systems may be broken down into identical components, each obeying simple laws, the huge number of components that make up the whole system act together to yield very complex behavior. In some cases this complex behavior may be simulated numerically with just a few components. But in most cases the simulation requires too many components, and this direct approach fails. One must instead attempt to distill the mathematical essence of the process by which complex behavior is generated. The hope in such an approach is to identify fundamental mathematical mechanisms that are common to many different natural systems. Such commonality would correspond to universal features in the behavior of very different complex natural systems. To discover and analyze the mathematical basis for the generation of complexity, one must identify simple mathematical systems that capture the essence of the process. Cellular automata are a candidate class of such systems. This article surveys their nature and properties, concentrating on fundamental mathematical features. Cellular automata promise to provide mathematical models for a wide variety of complex phenomema, from turbulence in fluids to patterns in biological growth. The general features of their behavior discussed here should form a basis for future detailed studies of such specific systems.

t

The Nature of Cellular Automata and a Simple Example
Cellular automata are simple mathematical idealizations of natural systems. They consist of a lattice of discrete identical sites, each site taking on a finite set of, say, integer values. The values of the sites evolve in discrete time steps according to deterministic rules that specify the value of each site in terms of the values of neighboring sites. Cellular automata may thus be considered as discrete idealizations of the partial differential equations often used to describe natural systems. Their discrete nature also allows an important analogy with digital computers: cellular automata may be viewed as parallelprocessing computers of simple construction. As a first example of a cellular automaton, consider a line of sites, each with value 0 or 1 (Fig. 1). Take the value of a site at position i for the time evolution of these site values is

1 0 1 1 0 1 0 0 0

1 1 0 1 0 1 1 0 1 0 0

Fig. 1. A typical configuration in the simple cellular automaton described by Eq. 1, consisting of a sequence of sites with values O or I. Sites with value 1 are represented by squares; those with value O are blank.

(1)

where mod 2 indicates that the O or 1 remainder after division by 2 is taken. According to this rule, the value of a particular site is given by the sum modulo 2 (or. equivalently, the Boolean algebra “exclusive or”) of the values of its left- and right-hand nearest neighbor sites on the previous time step. The rule is implemented simultaneously at each site. * Even with this very simple rule quite complicated behavior is nevertheless found. Fractal Patterns Grown from Cellular Automata. First of all, consider evolution ac-

*In the very simplest computer implementation a separate array of updated site values mast be maintained and copied back CO the original site value array when the updating process is complete. 4

Fig. 2. A few time steps in the evolution of the simple cellular automaton defined by Eq. I, starting from a “seed” containing a single nonzero site. Successive lines are obtained by successive applications of Eq. 1 at each site. According to this rule, the value of each site is the sum modulo 2 of the values of its two nearest neighbors on the previous time step. The pattern obtained with this simple seed is Pascal’s triangle of binomial coefficients, reduced modulo 2.
Fall 1983 LOS ALAMOS SCIENCE

Cellular Automata

cording to Eq. 1 from a “seed” consisting of a single site with value 1, all other sites having value O. The pattern generated by evolution for a few time steps already exhibits some structure (Fig. 2). Figure 3 shows the pattern generated after 500 time steps. Generation of this pattern required application of Eq. 1 to a quarter of a million site values. The pattern of Figs. 2 and 3 is an intricate one but exhibits some striking regularities. One of these is “self -similarity.” As illustrated in Fig. 3, portions of the pattern, when magnified, are indistinguishable from the whole. (Differences on small scales between the original pattern and the magnified portion disappear when one considers the limiting pattern obtained after an infinite number of time steps.) The pattern is therefore invariant under resealing of lengths. Such a self-similar pattern is often called a fractal and may be characterized by a fractal dimension. The fractal dimension of the pattern in Fig. 3, for example, is logz3 = log3/log2 = 1.59. Many natural systems, including snowflakes, appear to exhibit fractal patterns. (See Benoit B. Mandelbrot, The Fractal Geornetry of Nature, W. H. Freeman and Company, 1982. ) It is very possible that in many cases these fractal patterns are generated through evolution of cellular automata or analogous processes. Self-Organization in Cellular Automata. Figure 4 shows evolution according to Eq. 1 from a “disordered” initial state. The values of sites in this initial state are randomly chosen: each site takes on the value O or 1 with equal probability. independently of the values of other sites. Even though the initial state has no structure, evolution of the cellular automaton does manifest some structure in the form of many triangular “clearings.” The spontaneous appearance of these clearings is a simple example of “selforganization.” The pattern of Fig. 4 is strongly reminiscent of the pattern of pigmentation found on the shells of certain mollusks (Fig. 5). It is
5

Fig. 3. Many time steps in the evolution of the cellular automaton of Fig. 2, generated by applying the rule of Eq. 1 to about a quarter of a million site values. The pattern obtained is “self-similar”: a part of the pattern, when magnified, is indistinguishable from the whole. The pattern has a fractal dimension of log 23 = 1.59.
LOS ALAMOS SCIENCE Fall 1983

quite possible that the growth of these pigmentation patterns follows cellular automaton rules. In systems that follow conventional thermodynamics, t h e s e c o n d l a w o f thermodynamics implies a progressive degradation of any initial structure and a universal tendency to evolve with time to states of maximum entropy and maximum disorder. While many natural systems do tend toward disorder, a large class of systems, biological ones being prime examples, show a reverse trend: they spontaneously generate structure with time, even when starting from disordered or structureless initial states. The cellular automaton in Fig. 4 is a simple example of such a self-organizing system. The mathematical basis of this behavior is revealed by considering global properties of the cellular automaton. Instead of following evolution from a particular initial state, as in Fig. 4, one follows the overall evolution of an ensemble of many different initial states. It is convenient when investigating global properties to consider finite cellular automata that contain a finite number N of sites whose values are subject to periodic boundary conditions. Such a finite cellular automaton may be represented as sites arranged, for example. around a circle. If each site has two possible values, as it does for the rule of Eq. 1, there are a total of 2 n possible states, or configurations, for the complete finite cellular automaton. The global evolution of the cellular automaton may then be represented by a finite state transition graph plotted in the “state space” of the cellular automaton. Each of the 2 n possible states of the complete cellular automaton (such as the state 110101101010 for a cellular automaton with twelve sites) is represented by a node, or point, in the graph, and a directed line connects each node to the node generated by a single application of the cellular automaton rule. The trajectory traced out in state space by tbe directed lines connecting one particular node to its successors thus corresponds to the time evolution of the cellular 6

Fig. 4. Evolution of the simple cellular automaton defined by Eq. I, from a disordered initial state in which each site is taken to have value O or 1 with equal, independent probabilities. Evolution of the cellular automaton even from such a random initial state yields some simple structure.

Fig. 5. A “cone shell” with a pigmentation pattern reminiscent of the pattern generated by the cellular automaton of Fig. 4. (Shell courtesy of P. Hut.)
Fall 1983 LOS ALAMOS SCIENCE

Cellular Automata

Fig. 6. The global state transition graph for a finite cellular automaton consisting of twelve sites arranged around a circle and evolving according to the simple rule of Eq. 1. Each node in the graph represents one of the 4096 possible states, or sequences of the twelve site values, of the cellular automaton. Each node is joined by a directed line to a successor node that corresponds to the state obtained by one time step of cellular automaton evolution. The state transition graph consists of many disconnected pieces, many of identical structure. Only one copy of each structurally identical piece is shown explicitly. Possible paths through the state transition graph represent possible trajectories in the state space of the cellular automaton. The merging of these trajectories reflects the irreversibility of the cellular automaton evolution. Any initial state of this cellular automaton ultimately evolves to an “attractor” represented in the graph by a cycle. For this particular cellular automaton all configurations evolve to attractors in at most three time steps. (From O. Martin, A. Odlyzko, and S. Wolfram, “Algebraic Properties of Cellular Automata, ” Bell Laboratories report (January 1983) and to be published in Communications in Mathematical Physics.)
automaton from the initial state represented by that particular node. The state transition graph of Fig. 6 shows all possible trajectories in state space for a cellular automaton with twelve sites evolving according to the simple rule of Eq. 1. A notable feature of Fig. 6 is the presence of trajectories that merge with time. While each state has a unique successor in time, it may have several predecessors or no predecessors at all (as for states on the periphery
LOS ALAMOS SCIENCE Fall 1983

of the state transition graph). The merging of trajectories implies that information is lost in the evolution of the cellular automaton: knowledge of the state attained by the system at a particular time is not sufficient to determine its history uniquely, so that the evolution is irreversible. Starting with an initial ensemble in which all configurations occur with any distribution of probabilities. the irreversible evolution decreases the probabilities for some configurations and

increases those for others. For example, after just one time step the probabilities for states on the periphery of the state transition graph in Fig. 6 are reduced to zero; such states may be given as initial conditions, but may never be generated through evolution of the cellular automaton. After many time steps only a small number of all the possible configurations actually occur. Those that do occur may be considered to lie on “attractors” of the cellular automaton evolution. Moreover. if the attractor states have special “organized” features, these features will appear spontaneously in the evolution of the cellular automaton. The possibility of selforganization is therefore a consequence of the irreversibility of the cellular automaton evolution, and the structures obtained through self-organization are determined by the characteristics of the attractors. The irreversibility of cellular automaton evolution revealed by Fig, 6 is to be contrasted with the intrinsic reversibility of systems described by conventional thermodynamics. At a microscopic level the trajectories representing the evolution of states in such systems never merge: each state has a unique predecessor. and no information is lost with time, Hence a completely disordered ensemble, in which all possible states occur with equal probabilities, remains disordered forever. Moreover. if nearby states arc grouped (or “coarse-grained”) together. as by imprecise measurements, then with time the probabilities for different groups of states will tend to equality. regardless of their initial values. In this way such systems tend with time to complete disorder and maximum entropy. as prescribed by the second law of thermodynamics. Tendency to disorder and increasing entropy are universal features of intrinsically reversible systems in statistical mechanics. Irreversible systems, such as the cellular automaton of Figs. 2, 3, and 4, counter this trend, but universal laws have yet to be found for their behavior and for the structures they may generate. One hopes that such general laws may ultimately 7

be abstracted from an investigation of the comparatively simple examples provided by cellular automata. While there is every evidence that the fundamental microscopic laws of physics are intrinsically reversible (information-preserving, though not precisely time-reversal invariant), many systems behave irreversibly on a macroscopic scale and are appropriately described by irreversible laws, For example, while the microscopic molecular interactions in a fluid are entirely reversible, macroscopic descriptions of the average velocity field in the fluid, using, say, the Navier-Stokes equations, are irreversible and contain dissipative terms. Cellular automata provide mathematical models at this macroscopic level.

ing for each configuration a characteristic polynomial

where x is a dummy variable, and the coefficient of xi is the value of the site at position i. In terms of characteristic polynomials, the cellular automaton rule of Eq. 1 takes on the particularly simple form

and in fact is almost always equal to this value (the first exception occurs for N = 37), Here sord N (2) is a number theoretical function defined to be the minimum positive maximum value of sord N (2), typically achieved when N is prime, is (N–1)/2. The maximal cycle length is thus of order 2 N/2 , approximately the square root of the total number of possible states 2 N. An unusual feature of this analysis is the appearance of number theoretical concepts. Number theory is inundated with complex results based on very simple premises. It may be part of the mathematical mechanism by which natural systems of simple construction yield complex behavior,

where

T(x) =

(x + x-’)

Mathematical Analysis of a Simple Cellular Automaton

The cellular automaton rule of Eq. 1 is particularly simple and admits a rather complete mathematical analysis. The fractal patterns of Figs. 2 and 3 may be characterized in a simple algebraic manner. If no reduction modulo 2 were performed, then the values of sites generated from a single nonzero initial site would simply be the integers appearing in Pascal’s triangle of binomial coefficients. The pattern of nonzero sites in Figs. 2 and 3 is therefore the pattern of odd binomial coefficients in Pascal’s triangle. (See Stephen Wolfram, “Geometry of Binomial Coefficients,” to be published in American Mathematical

Monthly.)
This algebraic approach may be extended to determine the structure of the state transition diagram of Fig. 6. (See O. Martin, A. Odlyzko, and S. Wolfram, “Algebraic Properties of Cellular Automata,” Bell Laboratories report (January 1983) and to be published in Communications in Mathematical Physics,) The analysis proceeds by writ8

and all arithmetic on the polynomial coefficients is performed modulo 2. The reduction modulo xN –1 implements periodic boundary conditions. The structure of the state transition diagram may then be deduced from algebraic properties of the polynomial T(x). For even N one finds, for example, that the fraction of states on attractors is 2- D 2 ( N ) , where D 2(N) is defined as the largest integral power of 2 that divides N (for example, D 2(12) = 4). Since a finite cellular automaton evolves deterministically with a finite total number of possible states, it must ultimately enter a cycle in which it visits a sequence of states repeatedly. Such cycles are manifest as closed loops in the state transition graph. The algebraic analysis of Martin et al. shows that for the cellular automaton of Eq. 1 the maximal cycle length II (of which all other cycle lengths are divisors) is given for even N by

More General Cellular Automata

The discussion so far has concentrated on the particular cellular automaton rule given by Eq. 1. This rule may be generalized in several ways. One family of rules is obtained by allowing the value of a site to be an arbitrary function of the values of the site itself and of its two nearest neighbors on the previous time step:

or

A convenient notation illustrated in Fig. 7. assigns a “rule number” to each of the 256 rules of this type. The rule number of Eq. 1 is 90 in this notation. Further generalizations allow each site in a cellular automaton to take on an arbitrary Fall 1983 LOS ALAMOS SCIENCE

Cellular Automata

Universality Classes in Cellular Automata

Fig. 7. Assignment of rule numbers to cellular automata for which k = 2 and r = I. The values of sites obtained from each of the eight possible three-site neighborhoods are combined to form a binary number that is quoted as a decimal integer. The example shown is for the rule given by Eq. 1.

number k of values and allow the value of a site to depend on the values of sites at a distance up to r on both sides. so that

rated and simple; pattern; Class 4—evolution leads to complex structures, sometimes long-lived. Examples of these classes are indicated in Fig. 8. The existence of only four qualitative classes implies considerable universality in the behavior of cellular automata; many features of cellular automata depend only on the class in which they lie and not on the precise details of their evolution. Such universality is analogous, though probably not mathematically related, to the universality found in the equilibrium statistical mechanics of critical phenomena. In that case many systems with quite different detailed construction are found to lie in classes with critical exponents that depend only on general, primarily geometrical features of the systems and not on their detailed construction.

The number of different rules with given k k2r+1 and therefore becomes and r grows as k immense even for rather small k and r. Figure 8 shows examples of evolution according to some typical rules with various k and r values. Each rule leads to patterns that differ in detail. However, the examples suggest a very remarkable result: all patterns appear to fall into only four qualitative classes. These basic classes of behavior may be characterized empirically as follows: . Class l—evolution leads to a homogeneous state in which, for example, all sites have value O; stable or periodic structures that are sepaLOS ALAMOS SCIENCE Fall 1983

To proceed in analyzing universality in cellular automata, one must first give more quantitative definitions of the classes identified above. One approach to such definitions is to consider the degree of predictability of the outcome of cellular automaton evolution, given knowledge of the initial state. For class 1 cellular automata complete prediction is trivial: regardless of the initial state, the system always evolves to a unique homogeneous state. Class 2 cellular automata have the feature that the effects of particular site values propagate only a finite distance, that is, only to a finite number of neighboring sites. Thus a change in the value of a single initial site affects only a finite region of sites around it, even after an infinite number of time steps. This behavior, illustrated in Fig. 9, implies that prediction of a particular final site value requires knowledge of only a finite set of initial site values. In contrast, changes of initial site values in class 3 cellular automata, again as illustrated in Fig. 9, almost always propagate at a finite speed forever and therefore affect more and more distant sites as time goes on. The value of a particular site after many time steps thus depends on an ever-increasing number of initial site values. If the initial state is disordered, this dependence may lead to an apparently chaotic succession of values for a particular site. In class 3 cellular automata, therefore, prediction of the value of a site at infinite time would require knowledge of an infinite number of initial site values. Class 4 cellular automata are distinguished by an even greater degree of unpredictability, as discussed below. Class 2 cellular automata may be considered as “filters” that select particular features of the initial state. For example, a class 2 cellular automata may be constructed in which initial sequences 111 survive, but sites not in such sequences eventually attain
9

Fig. 9. Difference patterns showing the differences between configurations generated by evolution, according to various cellular automaton rules, from initial states that differ in the value of a single site. Each difference pattern is labeled by the behavior class of the cellular automaton rule. The effects of changes in a single site value depend on the behavior class of

the rule: for class 2 rules the effects have finite range; for class 3 rules the effects propagate to neighboring sites indefinitely at a fixed speed; and for class 4 rules the effects also propagate to neighboring sites indefinitely but at various speeds. The difference patterns shown here are analogues of Green’s functions for cellular automata.

value O. Such cellular automata are of practical importance for digital image processing: they may be used to select and enhance particular patterns of pixels. After a sufficiently long time any class 2 cellular automaton evolves to a state consisting of blocks containing nonzero sites separated by regions of zero sites. The blocks have a simple form. typically consisting of repetitions of particular site values or sequences of site values (such as 101010. . .). The blocks either do not change with time (yielding vertical stripes in the patterns of Fig. 8) or cycle between a few states (yielding “railroad track” patterns). While class 2 cellular automata evolve to give persistent structures with small periods, class 3 cellular automata exhibit chaotic aperiodic behavior, as shown in Fig. 8. Although chaotic, the patterns generated by class 3 cellular automata are not completely LOS ALAMOS SCIENCE Fall 1983

random. In fact, as mentioned for the example of Eq. 1, they may exhibit important selforganizing behavior. In addition and again in contrast to class 2 cellular automata, the statistical properties of the states generated by many time steps of class 3 cellular automaton evolution are the same for almost all possible initial states. The large-time behavior of a class 3 cellular automaton is therefore determined by these common statistical properties. The configurations of an infinite cellular automaton consist of an infinite sequence of site values. These site values could be considered as digits in a real number, so that each complete configuration would correspond to a single real number. The topology of the real numbers is. however, not exactly the same as the natural one for the configurations (the binary numbers 0.111111 . . . and 1.00000 . . . are identical,

but the corresponding configurations are not). Instead. the configurations of an infinite cellular automaton form a Cantor set. Figure 10 illustrates two constructions for a Cantor set. In construction (a) of Fig. 10. one starts with the set of real numbers in the interval O to 1. First one excludes the middle third of the interval, then the middle third of each interval remaining, and so on. In the limit the set consists of an infinite number of disconnected points. If positions in the interval are represented by ternimals (base 3 fractions, analogous to base 10 decimals). then the construction is seen to retain only points whose positions are represented by ternimals containing no 1‘s (the point 0.2202022 is therefore included; 0.2201022 is excluded). An important feature of the limiting set is its self-similarity. or fractal form: a piece of the set, when magnified, is indistinguishable from the whole. This self-similarity is math-

0
emetically analogous to that found for the limiting two-dimensional pattern of Fig. 3. In construction (b) of Fig. 10, the Cantor set is formed from the “leaves” of an infinite binary tree. Each point in the set is reached by a unique path from the “root” (top as drawn) of the tree. This path is specified by an infinite sequence of binary digits, in which successive digits determine whether the leftor right-hand branch is taken at each successive level in the tree. Each point in the Cantor set corresponds uniquely to one infinite sequence of digits and thus to one configuration of an infinite cellular automaton. Evolution of the cellular automaton then corresponds to iterated mappings of the Cantor set to itself. (The locality of cellular automaton rules implies that the mappings are continuous.) This interpretation of cellular automata leads to analogies with the theory of iterated mappings of intervals of the real line. (See Mitchell J. Feigenbaum, “Universal Behavior in Nonlinear Systems,” Los Alamos Science, Vol. 1, No. 1(1980): 4-27.) Cantor sets are parameterized by their “dimensions.” A convenient definition of dimension, based on construction (a) of Fig. 10, is as follows, Divide the interval from 0 to 1 into k17 bins, each of width k n. Then let N(n) be the number of these bins that contain points in the set. For large n this number behaves according to N(n) - kd ” . (2)

2

0
0

0
2

2

(b)

and d is defined as the “set dimension” of the Cantor set. If a set contained all points in the interval O to 1, then with this definition its dimension would simply be 1. Similarly, any finite number of segments of the real line would form a set with dimension 1. However, the Cantor set of construction (a’), which contains an infinite number of disconnected pieces, has a dimension according to An alternative definition of dimension, agreeing with the previous one for present 14

Fig. 10. Steps in two constructions of a Cantor set. At each step in construction (a), the middle third of all intervals is excluded. The first step thus excludes all points whose positions, when expressed as base 3 fractions, have a 1 in the first “ternimal place” (by analogy with decimal place), the second step excludes all points whose positions have a 1 in the second ternimal place, and so on. The limiting set obtained after an infinite number of steps consists of an infinite number of disconnected points whose positions contain no 1‘s. The set maybe assigned a dimension, according to Eq. Cantor set. Infinite sequences of digits, representing cellular automaton configurations, are seen to correspond uniquely with points in the Cantor set.
Fall 1983 LOS ALAMOS SCIENCE

Cellular Automata

Fig. 11. Time evolution of the probabilities for each of the 1024 possible configurations of a typical class 3 cellular automaton with k = 2 and r = I and of size 10, starting from an initial ensemble in which each possible configuration occurs with equal probability. The configurations are specified by integers whose binary digits form the sequence of site values. The probability for a particular configuration is given on successive lines in a vertical column: a dot appears at a particular time step if the configuration occurs with nonzero probability at that time step. In the initial ensemble all configurations occur with equal nonzero probabilities, and dots appear in all positions. The cellular automaton evolution modifies the probabilities for the configurations, making some occur with zero probability and yielding gaps in which no dots appear. This “thinning” is a consequence of the irreversibility of the cellular automaton evolution and is reflected in a decrease of entropy with time. In the limit of cellular automata of infinite size, the configurations appearing at large times form a Cantor set. For the rule shown (rule 18 in the notation of Fig. 7) the limiting dimension of this Cantor set is found to be approximately 0.88.
purposes. is based on self-similarity. Take the Cantor set of construction (a) in Fig. 10. Contract the set by a magnification factor k-m. By virtue of its self-similarity, the whole set is identical to a number, say M(m), o f copies of this contracted copy. For large m, set dimension. With these definitions the dimension of the Cantor set of all possible configurations for an infinite one-dimensional cellular automaton is 1. A disordered ensemble. in which each possible configuration occurs with equal probability, thus has dimension I. Figure 11 shows the behavior of the probabilities for the configurations of a typical cellular automaton as a function of time. LOS
ALAMOS SCIENCE Fall 1983

starting from such a disordered initial ensemble, As expected from the irreversibility of cellular automaton evolution, exemplified by the state transition graph of Fig. 6, different configurations attain different probabilities as evolution proceeds. and the probabilities for some configurations decrease to zero. This phenomenon is manifest in the “thinning” of configurations on successive time steps apparent in Fig. I I. The set of configurations that survive with nonzero probabilities after many time steps of cellular automaton evolution constitutes the “attractors” for the evolution. This set is again a Cantor set; for the example of Fig. 1.755 is the real solution of the polynomial

2 equation z3 – Z + 2 Z – 1 = 0. (See D. A. Lind, “Applications of Ergodic Theory and Sofic Systems to Cellular Automata.” University of Washington preprint (April 1983) and to be published in Physica D; see also Martin et al., op. cit.) The greater the irreversibility in the cellular automaton evolution, the smaller is the dimension of the Cantor set corresponding to the attractors for the evolution. If the set of attractors for a cellular automaton has dimension 1, then essentially all the configurations of the cellular automaton may occur at large times. If the attractor set has dimension less than 1. then a vanishingly small fraction of all possible configurations are generated after many time steps of evolution. The attractor sets for most class 3 cellular automata have dimensions less than 1. For those class 3 cellular automata that generate regular patterns, the more regular the pattern, the smaller is the dimension of the attractor set; these cellular automata are more irreversible and are therefore capable of a higher degree of self-organization. The dimension of a set of cellular automaton configurations is directly proportional to the limiting entropy (or information) per site of the sequence of site values that make up the configurations. (See Patrick Billingsley, Ergodic Theory and Information, John Wiley & Sons. 1965.) If the dimension of the set was 1, so that all possible sequences of site values could occur, then the entropy of these sequences would be maximal. Dimensions lower than 1 correspond to sets in which some sequences of site values are absent, so that the entropy is reduced. Thus the dimension of the attractor for a cellular automaton is directly related to the limiting entropy attained in its evolution, starting from a disordered ensemble of initial states. Dimension gives only a very coarse measure of the structure of the set of configurations reached at large times in a cellular automaton. Formal language theory may provide a more complete characterization of the set. “Languages” consist of a set

15

of words, typically infinite in number. formed from a sequence of letters according to certain grammatical rules. Cellular automaton configurations are analogous to words in a formal language whose letters are the k possible values of each cellular automaton site. A grammar then gives a succinct specification for a set of cellular automaton configurations. Languages may be classified according to the complexity of the machines or computers necessary to generate them. A simple class of languages specified by “regular grammars’” may be generated by finite state machines. A finite state machine is represented by a state transition graph (analogous to the state transition graph for a finite cellular automaton illustrated in Fig. 6). The possible words in a regular grammar are generated by traversing all possible paths in the state transition graph. These words may be specified by “regular expressions” consisting of finite length sequences and arbitrary repetitions of these, For example, the regular expression 1(00)* 1 represents all sequences containing an even number of O’s (arbitrary repetition of the sequence 00) flanked by a pair of 1’s. The set of configurations obtained at large times in class 2 cellular automata is found to form a regular language. It is likely that attractors for other classes of cellular automata correspond to more complicated languages.

Analogy with Dynamical Systems Theory
The three classes of cellular automaton behavior discussed so far are analogous to three classes of behavior found in the solutions to differential equations (continuous dynamical systems). For some differential equations the solutions obtained with any initial conditions approach a fixed point at large times. This behavior is analogous to class 1 cellular automaton behavior. in a second class of differential equations, the limiting solution at large times is a cycle in which the parameters vary periodically with time. These equations are analogous to class 2 cellular automata. Finally. some differential equations have been found to exhibit complicated, apparently chaotic behavior depending in detail on their initial conditions. With the initial conditions specified by decimals, the solutions to these differential equations depend on progressively higher and higher order digits in the initial conditions. This phenomenon is analogous to the dependence of a particular site value on pro16

Evolution of a class 4 cellular automaton from several disordered initial states. The bottom example has been reproduced on a larger scale to show detail. In this cellular automaton, for which k = 2 and r = 2, the value of a site is 1 only if a total of two or four sites out of the five in its neighborhood have the value 1 on the previous time step. For some initial states persistent structures are formed, some of which propagate with time. This cellular automaton is believed to support universal computation, so that with suitable initial states it may implement any finite algorithm.
Fall 1983 LOS ALAMOS SCIENCE

Cellular Automata

Fig. 13. Persistent structures exhibited by the class 4 cellular automaton of Fig. 12 as it evolves from initial states with nonzero sites in a region of twenty or fewer sites. These
gressively more distant initial site values in the evolution of a class 3 cellular automaton. The solutions to this final class of differential equations tend to “strange” or “chaotic” attractors (see Robert Shaw, “Strange Attractors, Chaotic Behavior, and Information Flow.” Zeitschrift fur Naturforschung 36A(1981):80), which form Cantor sets in direct analogy with those found in class 3 cellular automata. The correspondence between classes of behavior found in cellular automata and those found in continuous dynamical systems supports the generality of these classes. Moreover, the greater mathematical simplicity of cellular automata suggests that investigation of their behavior may elucidate the behavior of continuous dynamical systems.

structures are almost sufficient to demonstrate a universal computation capability for the cellular automaton.

simple patterns. In addition, the propagating structures allow site values at one position to affect arbitrarily distant sites after a sufficiently long time. No analogous behavior has yet been found in a continuous dynamical system. The complexity apparent in the behavior of class 4 cellular automata suggests the conjecture that these systems may be capable of universal computation. A computer may be regarded as a system in which definite rules are used to transform an initial sequence of. say, 1’s and O’s to a final sequence of 1‘s and 0’s. The initial sequence may be considered as a program and data stored in computer memory. and part of the final sequence may be considered as the result of the computation. Cellular automata may be considered as computers; their initial configurations represent programs and initial data, and their configurations after a long time contain the results of computations. A system is a universal computer if. given a suitable initial program, its time evolution can implement any finite algorithm. (See Frank S. Beckman, Mathematical Foundations of Programming. Addison-Wesley Publishing Co,, 1980.) A universal computer need thus only be “reprogrammed,” not “rebuilt,” to perform each possible calculation. (All modern general-purpose electronic digital computers are, for practical purposes. universal computers; mechanical adding machines were not. ) If a cellular automaton is to be a universal computer, then. with a fixed rule for its time evolution, different initial

A Universal Computation Class of Cellular Automata
Figure 12 shows patterns obtained by evolution from disordered initial states according to a class 4 cellular automaton rule. Complicated behavior is evident. In most cases all sites eventually “die” (attain value O). In some cases. however. persistent structures that survive for an infinite time are generated, and a few of these persistent structures propagate with time. Figure 13 shows all the persistent structures generated from initial states with nonzero sites in a region of twenty or fewer sites. Unlike the periodic structures of class 2 cellular automata, these persistent structures have no

configurations must encode all possible programs. The only known method of proving that a system may act as a universal computer is to show that its computational capabilities are equivalent to those of another system already classified as a universal computer. The Church-Turing thesis states that no system may have computational capabilities greater than those of universal computers. The thesis is supported by the proven equivalence of computational models such as Turing machines, string-manipulation systems, idealized neural networks. digital computers, and cellular automata. While mathematical systems with computational power beyond that of universal computers may be imagined, it seems likely that no such systems could be built with physical components. This conjecture could in principle be proved by showing that all physical systems could be simulated by a universal computer. The main obstruction to such a proof involves quantum mechanics. A cellular automaton may be proved capable of universal computation by identifying structures that act as the essential components of digital computers, such as wires, NAND gates, memories. and clocks. The persistent structures illustrated in Fig. 13 provide many of the necessary components, strongly suggesting that the cellular automaton of Figs. 12 and 13 is a universal computer. One important missing component is a “clock” that generates an infinite sequence of “pulses”; starting from an initial
17

configuration containing a finite number of nonzero sites, such a structure would give rise to an ever-increasing number of nonzero sites. If such a structure exists, it can undoubtedly be found by careful investigation, although it is probably too large to be found by any practical exhaustive search. If the cellular automaton of Figs. 12 and 13 is indeed capable of universal computation, then, despite its very simple construction, it is in some sense capable of arbitrarily complicated behavior. Several complicated cellular automata have been proved capable of universal computation. A one-dimensional cellular automaton with eighteen possible values at each site (and nearest neighbor interactions) has been shown equivalent to the simplest known universal Turing machine. In two dimensions several cellular automata with just two states per site and interactions between nearest neighbor sites (including diagonally adjacent sites, giving a nine-site neighborhood) are known to be equivalent to universal digital computers. The best known of these cellular automata is the “Game of Life” invented by Conway in the early 1970s and simulated extensively ever since. (See Elwyn R. Berlekamp, John H. Conway, and Richard K. Guy, Winning Ways, Academic Press, 1982 and Martin Gardner, Wheels, Life, and Other Mathematical Amusements, W. H. Freeman and Company, October 1983. The Life rule takes a site to have value 1 if three and only three of its eight neighbors are 1 or if four are 1 and the site itself was 1 on the previous time step.) Structures analogous to those of Fig. 13 have been identified in the Game of Life. In addition, a clock structure, dubbed the glider gun, was found after a long search. By definition, any universal computer may in principle be simulated by any other universal computer. The simulation proceeds by emulating the elementary operations in the first universal computer by sets of operations in the second universal computer, as in an “interpreter” program. The simulation is in general only faster or dower by a fixed finite factor, independent of the size or duration of a computation. Thus the behavior of a universal computer given particular input may be determined only in a time of the same order as the time required to run that universal computer explicitly. In general the behavior of a universal computer cannot be predicted and can be determined only by a procedure equivalent to observing the universal computer itself. If class 4 cellular automata are indeed 18

universal computers, then their behavior may be considered completely unpredictable. For class 3 cellular automata the values of particular sites after a long time depend on an ever-increasing number of initial sites. For class 4 cellular automata this dependence is by an algorithm of arbitrary complexity, and the values of the sites can essentially be found only by explicit observation of the cellular automaton evolution. The apparent unpredictability of class 4 cellular automata introduces a new level of uncertainty into the behavior of natural systems. The unpredictability of universal computer behavior implies that propositions concerning the limiting behavior of universal computers at indefinitely large times are formally undecidable. For example, it is undecidable whether a particular universal computer, given particular input data, will reach a special “halt” state after a finite time or will continue its computation forever. Explicit simulations can be run only for finite times and thus cannot determine such infinite time behavior. Results may be obtained for some special input data, but no general (finite) algorithm or procedure may even in principle be given. If class 4 cellular automata are indeed universal computers, then it is undecidable (in general) whether a particular initial state will ultimately evolve to the null configuration (in which all sites have value O) or will generate persistent structures. As is typical for such generally undecidable propositions, particular cases may be decided. In fact, the halting of the cellular automaton of Figs. 12 and 13 for all initial states with nonzero sites in a region of twenty sites has been determined by explicit simulation. In general, the halting probability, or fraction of initial configurations ultimately evolving to the null configuration, is a noncomputable number. However, the explicit results for small initial patterns suggest that for the cellular automaton of Figs. 12 and 13, this halting probability is approximately 0.93. In an infinite disordered configuration all possible sequences of site values appear at some point, albeit perhaps with very small probability. Each of these sequences may be considered to represent a possible “program”; thus with an infinite disordered initial state, a class 4 automaton may be considered to execute (in parallel) all possible programs. Programs that generate structures of arbitrarily great complexity occur, at least with indefinitely small probabilities. Thus, for example, somewhere on the infinite line a sequence that evolves to a self-reproducing

structure should occur. After a sufficiently long time this configuration may reproduce many times, so that it ultimately dominates the behavior of the cellular automaton. Even though the a priori probability for the occurrence of a self-reproducing structure in the initial state is very small, its a posteriori probability after many time steps of cellular automaton evolution may be very large. The possibility that arbitrarily complex behavior seeded by features of the initial state can occur in class 4 cellular automata with indefinitely low probability prevents the taking of meaningful statistical averages over infinite volume (length). It also suggests that in some sense any class 4 cellular automaton with an infinite disordered initial state is a microcosm of the universe. In extensive samples of cellular automaton rules, it is found that as k and r increase, class 3 behavior becomes progressively more dominant, Class 4 behavior occurs only fork > 2 or r > 1; it becomes more common for larger k and r but remains at the few percent level. The fact that class 4 cellular automata exist with only three values per site and nearest neighbor interactions implies that the threshold in complexity of construction necessary to allow arbitrarily complex behavior is very low. However, even among systems of more complex construction, only a small fraction appear capable of arbitrarily complex behavior. This suggests that some physical systems may be characterized by a capability for class 4 behavior and universal computation; it is the evolution of such systems that may be responsible for very complex structures found in nature. The possibility for universal computation in cellular automata implies that arbitrary computations may in principle be performed by cellular automata. This suggests that cellular automata could be used as practical parallel-processing computers. The mechanisms for information processing found in most natural systems (with the exception of those, for example, in molecular genetics) appear closer to those of cellular automata than to those of Turing machines or conventional serial-processing digital computers. Thus one may suppose that many natural systems could be simulated more efficiently by cellular automata than by conventional computers. In practical terms the homogeneity of cellular automata leads to simple implementation by integrated circuits. A simple one-dimensional universal cellular automaton with perhaps a million sites and a time step as short as a billionth of a second could perhaps be fabricated with current Fall 1983 LOS ALAMOS SCIENCE

Cellular Automata

Fig. 14. Simulation network for symmetric cellular automaton rules with k = 2 and r = I. Each rule is specified by the number obtained as shown in Fig. 7, and its behavior class is indicated by shades of gray: light gray corresponds to class 1, medium gray to class 2, and dark gray to class 3. Rule A is considered to simulate rule B if there exist blocks of site values that evolve under rule A as single sites would evolve under rule B.
technology on a single silicon wafer (the onedimensional homogeneous structure makes defects easy to map out). Conventional programming methodology is, of course, of little utility for such a system. The development of a new methodology is a difficult but important challenge. Perhaps tasks such as image processing, which are directly suitable for
LOS ALAMOS SCIENCE Fall 1983

Simulations are included in the network shown only when the necessary blocks are three or fewer sites long. Rules 90 and 150 are additive class 3 rules, rule 204 is the identity rule, and rules 170 and 240 are left- and right-shift rules, respectively. Attractive simulation paths are indicated by bold lines. (Network courtesy of J. Milnor.)

cellular automata, should be considered first.

A Basis for Universality?
The existence of four classes of cellular automata was presented above as a largely

empirical result. Techniques from computation theory may provide a basis, and ultimately a proof, of this result. The first crucial observation is that with special initial states one cellular automaton may behave just like another. In this way one cellular automaton may be considered to “simulate” another. A single site with a
19

Cellular Automata

cellular Automata,” to be published in Physica D.) Thus the simulation of rule 90 by rule 18 may be considered an “attractive” one: starting from almost all initial states, rule 18 evolves toward states in which it simulates rule 90. In general, one expects that some paths in the network of Fig. 14 are attractive, while the rest are repulsive. The consequences of a repulsive simulation path are illustrated in Fig. 16: with special initial states rule 94 behaves like rule 90, but any impurities in the initial states grow and eventually dominate the evolution of the system. Class 1 cellular automata have an attractive simulation path to rule O (or its equivalents). Class 2 cellular automata have attractive simulation paths to the identity rule 204. A conjecture for which some evidence exists is that all class 3 rules exhibit attractive simulations has to additive rules such as 90 or 150. Simulation by blocking of site values is analogous to a block spin or renormalization group transformation: additive rules have the special property that they are invariant under such transformations. As mentioned earlier, class 4 cellular automata are distinguished by the. presence of simulation paths leading to every other cellular automaton rule. It is likely that no specific path is distinguished as attractive. Cellular automata of different classes may thus be distinguished by their limiting behavior under simulation transformations. This approach suggests that classification of the qualitative behavior of cellular automata may be related to determinations of equivalence of systems and problem classes in computation theory. In general, one may hope for fundamental connections between computation theory and the theory of complex nonequilibrium statistical systems. Information theory forms a mathematical basis for equilibrium statistical mechanics. Computation theory, which addresses time-dependent processes. may be expected to play a fundamental role in nonequilibrium statistical mechanics. s
Los Alamos Science Fall 1983

Stephen Wolfram was born in London, England in 1959. He was educated at Eton College, Oxford University, and the California Institute of Technology where he received his Ph.D. in theoretical physics in 1979. He was a member of the faculty at Caltech from 1980 until he resigned in 1982. At that time he joined the Institute for Advanced Study in Princeton, New Jersey. He has worked in various areas of theoretical physics, including high-energy physics, cosmology, and statistical mechanics and has also worked in computer science, particularly in the area of symbolic computation. He received a MacArthur Fellowship in 1981 and since 1982 has been a Visiting Staff Member of the Theoretical Division at Los Alamos.

Acknowledgments
I am grateful to many people for discussions and suggestions. I thank in particular my collaborators in various cellular automaton investigations: O. Martin. J. Milnor, and A. Odlyzko. The research described here was supported in part by the Office of Naval Research under contract number N00014-80-C-0657.

Further Reading
John von Neumann. Edited and completed by Arthur W. Burks. Theory of Self-Reproducirg Automata. Urbana: University of Illinois Press, 1966. Arthur W. Burks, editor. Essays on Cellular Automata. Urbana: University of IIIinois Press, 1970. Stephen Wolfram. ‘cStatistical Mechanics of Cellular Automata.” Reviews of Modern Physics 55(1983):601 Stephen Wolfram. “Universality and Complexity in Cellular Automata.” The Institute for Advanced Study preprint (May 1983) and to be published in Physica D. Stephen Wolfram, J. Doyne Farmer, and Tommaso Toffoli, editors. “Cellular Automata: Proceedings of an Interdisciplinary Workshop (LOS Alamos; March 7-11. 1983).” TO be published in Physica D and to be available separately from North-Holland Publishing Company. 21

.—. HISTORICAL PERSPECTIVE

From Turing and von Neumann to the Present
by Necia G. Cooper
automaton—a mechanism that is relatively self-operating; a device or machine designed to follow automatically a predetermined sequence of operations or respond to encoded instructions. Before World War II Turing had proved the logical limits of computability and on the basis of this work had designed in idealized terms a universal computer, a machine that could perform all possible numerical computations. This idealized machine is now known as a Turing machine. (All modern computers have capabilities equivalent to some of the universal Turing machines.) During World War H Turing successfully applied his logical talent to the real and urgent problem of breaking the Nazi intelligence code. a feat that played a crucial role in the Allied victory. Prior to World War II von Neumann was aware of Turing’s work on computing machines and realized how useful such machines would be for investigating nonlinear problems in mathematical physics, in particular. the fascinating problem of turbulence. Numerical calculations might, for example, elucidate the mysterious role of the Reynolds number in turbulent phenomena. (The Reynolds number gives roughly the ratio of the inertial forces to the viscous forces. A flow that is regular becomes turbulent when this number is about 2000.) He was convinced that the best mathematics proceeds from empirical science and that numerical calculation on electronic computers might provide a new kind of empirical data on the properties of nonlinear equations. Stan Ulam suggests that the final impetus for von Neumann to work energetically on computer methods and design came from wartime Los Alamos, where it became obvious that analytical work alone was often not sufficient to provide even qualitative answers about the behavior of an atomic bomb. The best way to construct a computing machine thus presented a practical as well as a theoretical problem. Starting in 1944 von Neumann formulated methods of translating a set of mathematical procedures into a language of instructions for a computing machine. Before von Neumann’s work on the logical design of computers, the few existing electronic machines had to be rewired for each new problem. Von Neumann developed the idea of a fixed “flow diagram” and a stored “code,” or program, that would enable a machine with a fixed set of connections to solve a great variety of problems. Von Neumann was also interested, as was Turing, in discovering the logical elements Fall 1983 LOS ALAMOS SCIENCE

The notion of automata in the sense of machines that operate on their own from encoded instructions is very ancient, and one might say that mechanical clocks and music boxes fall under this category. The idea of computing machines is also very old. For instance. Pascal and Leibnitz outlined various schematics for such machines. In the latter part of the 18th century Baron de Kempelen built what was alleged to be the first chess-playing machine. Remarkable as it appeared. alas, it was a fake operated by a person hidden within it! The modern theory of automata can be traced to two giants in the field of mathematics. Alan Turing and John von Neumann. These two men laid much of the logical foundation for the development of present-day electronic computers, and both were involved in the practical design of real computing machines. 22

Cellular Automata

HISTORICAL —.
and organization required to perform some of the more general types of functions that human beings and other life forms carry out and in trying to construct, at least at an abstract level, machines that contained such capabilities. But whereas Turing was primarily interested in developing “intelligent” automata that would imitate the thinking and decision-making abilities of the human brain, von Neumann focused on the broader problem of developing a general theory of complicated automata, a theory that would encompass both natural automata (such as the human nervous system and living organisms) and artificial automata (such as digital computers and communication networks). What is meant by the term “complicated”? As von Neumann put it, it is not a question of how complicated an object is but rather of how involved or difficult its purposive operations are. In a series of lectures delivered at the University of Illinois in 1949, von Neumann explored ideas about what constitutes complexity and what kind of a theory might be needed to describe complicated automata. He suggested that a new theory of information would be needed for such systems, one that would bear a resemblance to both formal logic and thermodynamics. It was at these lectures that he explained the logical machinery necessary to construct an artificial automaton that could carry out one very specific complicated function, namely, self-reproduction. Such an automaton was also logically capable of constructing automata more complex than itself. Von Neumann actually began constructing several models of selfreproducing automata. Based on an inspired suggestion by Ulam, one of these models was in the form of a “cellular” automaton (see the preceding article in this issue by Stephen Wolfram for the definition of a cellular automaton). From the Illinois lectures it is clear that von Neumann was struggling to arrive at a correct definition of complexity. Although his thoughts were still admittedly vague, they
LOS ALAMOS SCIENCE Fall 1983

PERSPECTIVE

do seem, at least in some respects, related to the present efforts of Wolfram to find universal features of cellular automaton behavior and from these to develop new laws, analogous to those of thermodynamics, to describe self-organizing systems. Von Neumann suggested that a theory of information appropriate to automata would build on and go beyond the results of Turing, Godel, Szilard, and Shannon. Turing had shown the limits of what can be done with certain types of information—namely, anything that can be described in rigorously logical terms can be
done by an automaton. and, conversely.

anything that can be done by an automaton can be described in logical terms. Turing constructed. on paper, a universal automaton that could perform anything that any other automaton could do. It consisted of a finite automaton, one that exists in a finite number of states, plus an indefinitely extendible tape containing instructions. “The importance of Turing’s research is just this:” said von Neumann, “that if you construct an automaton right, then any additional requirements about the automaton can be handled by sufficiently elaborate instructions. This is true only if [the automaton] is sufficiently complicated. if it reaches a certain minimum level of complexity” (John von Neumann, Theory of Self-Reproducing Automata, edited and completed by Arthur W. Burks, University of Illinois Press, 1966, p. 50). Turing also proved that there are some things an automaton cannot do. For example, “Y OU cannot construct an automaton which can predict in how many steps another automaton which can solve a certain problem will actually solve it. . . . In other words, you can build an organ which can do anything that can be done. but you cannot build an organ which tells you whether it can be done” (ibid., p. 51). This result of Turing’s is connected with Godel’s work on the hierarchy of types in formal logic. Von Neumann related this result to his notion of complexity. He suggested that for objects of

low complexity, it is easier to predict their properties than to build them, but for objects of high complexity, the opposite is true. Von Neumann stated that the new theory of information should include not only the strict and rigorous considerations of formal logic but also statistical considerations. The reason one needs statistical considerations is to include the possibility of failure. The actual structure of both manmade and artificial automata is dictated by the need to achieve a state in which a majority of all failures will not be lethal. To include failure, one must develop a probabilistic system of logic. Von Neumann felt that the theory of entropy and information in thermodynamics and Shannon’s information theory would be relevant. Szilard had shown in 1929 that entropy in a physical system measures the lack of information; it gives the total amount of missing information on the microscopic structure of the system. Entropy defined as a physical quantity measures the degree of degradation suffered by any form of energy. “There are strong indications that information is similar to entropy and that the degenerative processes of entropy are paralleled by degenerative processes in the processing of information” (ibid., p. 62). Shannon’s work focused on the problem of transmitting information. He had developed a quantitative theory of measuring the capacity of a communication channel, a theory that included the role of redundancy. Redundancy makes it possible to correct errors and “is the only thing which makes it possible to write a text which is longer than, say, ten pages. In other words, a language which has maximum compression would actually be completely unsuited to conveying information beyond a certain degree of complexity, because you could never find out whether a text is right or wrong” (ibid., p. 60). Von Neumann emphasized the ability of living organisms to operate across errors. Such a system “is sufficiently flexible and
23

HISTORICAL PERSPECTIVE
well organized that as soon as an error shows up in any one part of it, the system automatically senses whether this error matters or not. If it doesn’t matter, the system continues to operate without paying any attention to it. If the error seems to be important, the system blocks that region out. by-passes it and proceeds along other channels. The system then analyzes the region separately at leisure and corrects what goes on there. and if correction is impossible the system just blocks the region off and bypasses it forever. . . . “To apply the philosophy underlying natural automata to artificial automata we must understand complicated mechanisms better than we do, we must have elaborate statistics about what goes wrong, and we must have much more perfect statistical information about the milieu in which a mechanism lives than we now have. An automaton cannot be separated from the milieu to which it responds” (ibid., p p . 71-72). From artificial automata “one gets a very strong impression that complication, or productive potentiality in an organization, is degenerative, that an organization which synthesizes something is necessarily more complicated. of a higher order, than the organization it synthesizes” (ibid., p. 79). But life defeats degeneracy. Although the complicated aggregation of many elementary parts necessary to form a living organism is thermodynamically highly improbable, once such a peculiar accident occurs. the rules of probability do not apply because the organism can reproduce itself provided the milieu is reasonable—and a reasonable milieu is thermodynamically much less improbable. Thus probability leaves a loophole that is pierced by self-reproduction. Is it possible for an artificial automaton to reproduce itself? Further, is it possible for a machine to produce something that is more complicated than itself in the sense that the offspring can perform more difficult and involved tasks than the progenitor? These 24

A three-dimensional object grown from a single cube to the thirtieth generation (dark cubes). The model shows only one octant of the three-dimensional structure. This figure and the two others illustrating this article are from R. G. Schrandt and S. M. Ulam, “On Recursively Defined Geometrical Objects and Patterns of Growth,” Los Alamos Scientific Laboratory report LA-3762, November 1967 and are also reprinted in Arthur W. Burks, editor, Essays on Cellular Automata, University of Illinois Press, 1970.

questions arise from looking at natural automata. In what sense can a gene contain a description of the human being that will come from it? How can an organism at a low level in the phylogenetic order develop into a higher level organism? From his comparison of natural and

artificial automata, von Neumann suggested
that complexity has one decisive property, namely, a critical size below which the process of synthesis is degenerative and above which the process is explosive in the sense that an automaton can produce others

that are more complex and of higher potentiality than itself. However, to get beyond the realm of vague statements and develop a correct formulation of complexity, he felt it was necessary to construct examples that exhibit the “critical and paradoxical properties of complication” (ibid., p. 80). To this end he set out to construct, in

principle, self-reproducing automata, automata “which can have outputs something
like themselves” (ibid., p. 75). (All artificial automata discussed up to that point. such as Turing machines, computing machines, and Fall 1983 LOS ALAMOS SCIENCE

Cellular Automata

HISTORICAL PERSPECTIVE

the network of abstract neurons discussed by McCulloch and Pitts (“A Logical Calculus of the Ideas Immanent in Nervous Activity,”

Bulletin of Mathematical Biophysics, 1943),
had inputs and outputs of completely different media than the automata themselves.) "There is no question of producing matter out of nothing. Rather, one imagines automata which can modify objects similar to themselves, or effect syntheses by picking up parts and putting them together, or take synthesized entities apart” (ibid., p. 75). Von Neumann drew up a list of unambiguously defined parts for the kinematic model of a self-reproducing automaton. Although this model ignored mechanical and chemical questions of force and energy, it did involve problems of movement, contact, positioning, fusing, and cutting of elements. Von Neumann changed his initial approach after extensive discussions with Ulam. Ulam suggested that the proof of existence and construction of a selfreproducing automaton might be done in a simpler, neater way that retained the logical and combinatorial aspects of the problem but eliminated complicated aspects of geometry and motion. Ulam’s idea was to construct the automaton in an indefinitely large space composed of cells. In two dimensions such a cellular structure is equivalent to an infinite checkerboard. The elements of the automaton are a set of allowable states for each cell. including an empty, or quiescent, state, and a transition rule for transforming one state into another. The rule defines the state of a cell at time interval t+1 in terms of its own state and the states of certain neighboring cells at time interval t. Motion is replaced by transmitting information from cell to cell; that is, the transition rule can change a quiescent cell into an active cell. Von Neumann’s universal self-reproducing cellular automaton, begun in 1952, was a rather baroque construction in which each cell had twenty-nine allowable states and a 25

(a)

(b)

A “contest’’ between two patterns, one of lines within squares (shaded) and one of dots within squares, growing in a 23 by 23 checkerboard. Both patterns grow by a recursive rule stating that the newest generation (represented by diagonal lines or by dots in an x shape) may occupy a square if that square is orthogonally contiguous to one and only one square occupied by the immediately preceding generation (represented by perpendicularly bisecting lines or by dots in a + shape). In addition, no piece of either pattern may survive more than two generations. Initially, the line pattern occupied only the lower left corner square, and the dot pattern occupied only the square immediately to the left of the upper right corner square. (a) At generation 16 the two patterns are still separate. (b) At generation 25 the two patterns engage. (c)At 32 generations the dot pattern has penetrated enemy territory. (d) At 33 generations the dot pattern has won the contest.
LOS ALAMOS SCIENCE Fall 1983

HISTORICAL PERSPECTIVE

neighborhood consisting of the four cells orthogonal to it. Influenced by the work of McCulloch and Pitts, von Neumann used a physiological simile of idealized neurons to help define these states. The states and transition rules among them were designed to perform both logical and growth operations. He recognized. of course. that his construction might not be the minimal or optimal one, and it was later shown by Edwin Roger Banks that a universal selfreproducing automaton was possible with only four allowed states per cell. The logical trick employed to make the automaton universal was to make it capable of reading any axiomatic description of any other automaton, including itself, and to include its own axiomatic description in its memory. This trick was close to that used by Turing in his universal computing machine. The basic organs of the automaton included a tape unit that could store information on and read from an indefinitely extendible linear array of cells, or tape, and a constructing unit containing a finite control unit and an indefinitely long constructing arm that could construct any automaton whose description was stored in the tape unit. Realization of the 29-state self-reproducing cellular automaton required some 200,000 cells. Von Neumann died in 1957 and did not complete this construction (it was completed by Arthur Burks). Neither did he complete his plans for two other models of selfreproducing automata. In one, based on the 29-state cellular automaton, the basic element was to be neuron-like and have fatigue mechanisms as well as a threshold for excitation. The other was to be a continuous model of self-reproduction described by a system of nonlinear partial differential equations of the type that govern diffusion in a fluid. Von Neumann thus hoped to proceed from the discrete to the continuous. He was inspired by the abilities of natural automata and emphasized that the nervous system was not purely digital but was a mixed analog-digital system. 26

Much effort since von Neumann’s time has gone into investigating the simulation capabilities of cellular automata. Can one define appropriate sets of states and transition rules to simulate natural phenomena’? Ulam was among the first to use cellular automata in this way. He investigated growth patterns of simple finite systems, simple in that each cell had only two states and obeyed some simple transition rule. Even very simple growth rules may yield highly complex patterns, both periodic and aperiodic. “The main feature of cellular automata,” Ulam points out, “is that simple recipes repeated many times may lead to very complicated behavior. Information analysts might look at some final pattern and infer that it contains a large amount of information, when in fact the pattern is generated by a very simple process. Perhaps the behavior of an animal or even ourselves could be reduced to two or three pages of simple rules applied in turn many times!" (private conversation. October 1983). Ulam’s study of the growth patterns of cellular automata had as one of its aims “to throw a sidelight on the question of how much ‘information’ is necessary to describe the seemingly enormously elaborate structures of living objects” (ibid.). His work with Holladay and with Schrandt on an electronic computing machine at Los Alamos in 1967 produced a great number of such patterns. Properties of their morphology were surveyed in both space and time. Ulam and Schrandt experimented with “contests” in which two starting configurations were allowed to grow until they collided. Then a fight would ensue, and sometimes one configuration would annihilate the other. They also explored three-dimensional automata. Another early investigator of cellular automata was Ed Fredkin. Around 1960 he began to explore the possibility that all physical phenomena down to the quantum mechanical level could be simulated by cellular automata. Perhaps the physical world is a discrete space-time lattice of

A pattern grown according to a recursive rule from three noncontiguous squares at the vertices of an approximately equilateral triangle. A square of the next generation is formed if (a) it is contiguous to one and only one square of the current generation, and (b) it touches no other previously occupied square except if the square should be its “grandparent. ” In addition, of this set of prospective squares of the (n+l)th generation satisfying condition (b), all squares that would touch each other are eliminated. However, squares that have the same parent are allowed to touch.
information bits that evolve according to simple rules. In other words, perhaps the universe is one enormous cellular automaton. There have been many other workers in this field. Several important mathematical results on cellular automata were obtained by Moore and Holland (University of Michigan) in the 1960s. The “Game of Life,” an example of a two-dimensional cellular automaton with very complex behavior, was invented by Conway (Cambridge University) around 1970 and extensively investigated for several years thereafter. Fall 1983 LOS ALAMOS SCIENCE

Cellular Automata

HISTORICAL PERSPECTIVE
in the formulation of general laws for complex self-organizing systems. He says that what he is looking for is a new concept—maybe it will be complexity or maybe something else—that like entropy will be always increasing (or decreasing) in such a system and will be manifest in both the microscopic laws governing evolution of the system and in its macroscopic behavior. It may be closest to what von Neumann had in mind as he sought a correct definition of’ complexity. We can never know. We can

Cellular automata have been used in biological studies (sometimes under the names of “tessellation automata” or “homogeneous structures”) to model several aspects of the growth and behavior of organisms. They have been analyzed as parallel-processing computers (often under the name of “iterative arrays”). They have also been applied to problems in number theory under the name “stunted trees” and have been considered in ergodic theory, as endomorphisms of the “dynamical” shift system. A workshop on cellular automata at Los Alamos in March 1983 was attended by researchers from many different fields. The proceedings of this workshop will be published in the journal Physica D and will also be issued as a book by North-Holland Publishing Co. In all this effort the work of Stephen Wolfram most closely approaches von Neumann’s dream of abstracting from examples of complicated automata new concepts rele-

vant to information theory and analogous to the concepts of thermodynamics. Wolfram has made a systematic study of one-dimensional cellular automata and has identified four general classes of behavior, as described in the preceding article. Three of these classes exhibit behavior analogous to the limit points, limit cycles, and strange attractors found in studies of nonlinear ordinary differential equations and transformation iterations. Such equations characterize dissipative systems. systems in which structure may arise spontaneously even from a disordered initial state. Fluids and living organisms are examples of such systems. (Non-dissipative systems, in contrast, tend toward disordered states of maximal entropy and are described by the laws of thermodynamics.) The fourth class mimics the behavior of universal Turing machines. Wolfram speculates that his identification of universal classes of behavior in cellular automata may represent a first step

Acknowledgment I wish to thank Arthur W. Burks for permission to reprint quotations from Theory of Self-Reproducing Automata. We are indebted to him for editing and completing von Neumann’s manuscripts in a manner that retains the patterns of thought of a great mind.

Further Reading
John von Neumann. Theory of Self-Reproducing Automata. Edited and completed by Arthur W. Burks. Urbana: University of Illinois Press. 1966. Part I is an edited version of the lectures delivered at the University of Illinois. Part II is von Neumann’s manuscript describing the construction of his 29-state self-reproducing automaton. Arthur W. Burks, editor. Essays on Cellular Automata. Urbana: University of Illinois Press. 1970. This volume contains early papers on cellular automata including those of Ulam and his coworkers. Andrew Hodges, “Alan Turing: Mathematician and Computer Builder.” New Scientist. 15 September 1983, pp. 789-792. This contains a wonderful illustration, “A Turing Machine in Action.” Martin Gardner. "On Cellular Automata, Self-Reproduction, the Garden of Eden. and the Game ‘Life,’ “ Scientific American, October 1971. The following publications deal with complexity per se: W. A. Beyer, M. L. Stein, and S. M. Ulam. “The Notion of Complexity.” Los Alamos Scientific Laboratory report LA-4822. December 1971. S. Winograd. Arithmetic Complexity of Computations. Philadelphia: Society of Industrial and Applied Mathematics. 1980.

LOS ALAMOS SCIENCE Fall 1983

27