|
Cellular Automata (1983) |
|
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 parallel-processing 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 
on time step 
to be 
. One very simple rule for the time evolution of these site values is
where mod 2 indicates that the 0 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. (1) Even with this very simple rule quite complicated behavior is nevertheless found.
First of all, consider evolution according to Eq. 1 from a ''seed'' consisting of a single site with value 1, all
other sites having value 0. 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 rescaling 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 
. Many natural systems, including snowflakes, appear to exhibit fractal patterns. (See Benoit B. Mandelbrot, The Fractal Geometry 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.
[ Figure 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 
.
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 0 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 ''self-organization.''
The pattern of Fig. 4 is strongly reminiscent of the pattern of pigmentation found on the shells of certain mollusks (Fig. 5). It is quite possible that the growth of these pigmentation patterns follows cellular automaton rules.
In systems that follow conventional thermodynamics, the second law of 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 
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 
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 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 the directed lines connecting one particular node to its successors thus corresponds to the time evolution of the cellular 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 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 such self-organization 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 are 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 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.
