Cellular
Automata, Dynamics and Complexity:
What is missing from "A New
Kind of Science"
"Apart from the unknown, everything is
obvious."
This is how ZORAC, the fictional alien artificial intelligence
entity from James Hogan's
novels "The Giants Series" often capped its analyses of
complicated situations. I was reminded of this oddly black and
white characterization of reality recently while reading about
Stephen Wolfram's "Principle of Computational
Equivalence." He states his PCE in layman terms as "Almost
all processes that are not obviously simple can be viewed as
computations of equivalent sophistication." By
"not obviously simple" Wolfram means
"universal" and in particular, so complex as to defy
conventional mathematical characterizations, a little like the
ZORACian algorithmic "unknown." The PCE is certainly a
profound statement with intriguing consequences, and Wolfram
makes a good case for it in over 1200 pages of prose that is
generously sprinkled with splendid graphics. However, I believe
that Wolfram applies the PCE far more broadly than is warranted.
The very presumption that all things might be understood
solely in computational terms misses the important relational
aspect of the mathematical method (the deep stuff of proofs,
which Wolfram unwisely considers inessential). If you are
wondering what I mean, then read on...
The book "A New Kind of Science" [1] (ANKS for short) came out a little over a year ago. That was some 30 years or more after several remarkably deep results for maps in one dimension appeared in print (e.g., Sharkovski's ordering of cycles). As there is hardly a mention of any of them or of related ideas in ANKS or in other works by Wolfram, I will try here to highlight the relationship between them and the basic notions in ANKS. The main part of my argument is an example (call it Logistic Automata because it is derived from the bifurcation diagram of the logistic equation) that generates complex behavior in ANKS terms (i.e., "class 4") yet the nature of its behavior is totally amenable to rigorous mathematical analysis. Although the mathematics that explains the complexity in my example is sophisticated, I will use an informal ANKS-style presentation (using pictures rather than equations) in order to reach as broad an audience as is possible.
Good reviews of ANKS are available in print (e.g., [2] and [3], the latter being more accurate technically) so I will not present another review here. There is also "Reflections..." on ANKS, an article by Raymond Kurzweil on the web that examines broader philosophical issues relating to ANKS. For updates and more details relating to ANKS go to its official website Wolfram Science. Though equationless and with repetitive prose, ANKS was mostly fun to read and the pictures were remarkable (both for their abundance and helpful contents). However, as far as cellular automata and discrete dynamics are concerned, Wolfram's works in the 1980's (see [4] or go to Wolfram's Publications on the web) are more interesting and substantial than the highly ambitious and speculative ANKS.
I will begin these notes with a quick introduction to the one-dimensional cellular automata, then proceed to a description of these in the standard dynamics language. After that I will discuss ANKS-type complexity concerns within the context of dynamic systems that are computationally complex and yet may be thoroughly analyzed non-computationally. This presentation in not intended (and does not) take anything away from the fascinating theory and applications of cellular automata. But it possibly demonstrates how ANKS comes up short in certain areas by proposing greater reliance on computation and visualization at the expense of detailed, formal mathematical analysis of the intricate relational fabric of deterministic dynamical systems.
The simplest cellular automata. The primary tools (and sources of inspiration) for much of what is in ANKS are discrete dynamical systems known as cellular automata (or CA for short). A good internet source for getting aquainted with various facets of CA is David Griffeath's remarkable website. The most popular (and widely applied) types of CA are the two-dimensional ones like the "Game of Life." But here I would like to focus on some dynamics issues related to the simplest possible CA, namely, the one-dimensional variety. These can be thought of as "cells" laid out on a line (the infinite case) or on a ring or circle (the finite case). The cells can be active or "alive" with one or more "colors." If only two colors are involved (say black and white) then the cells are either on (alive) or off (dead).
CA are turned into discrete dynamical systems by specifying update rules that determine the color of each cell at each instant of time based on colors in the immediately preceding instant (an initial start-up configuration is assumed given as initial conditions). The rules are typically local, i.e., the color of a cell at time n is determined by the colors of neighboring cells at time n-1. The simplest of such local rules are the 3-point ones; i.e., those involving the cell and its immediate neighbors to the right and to the left. Finally, if all the cells change color simultaneously, the CA are parallel, but if they change color one by one (in the finite case) then the CA is sequential. I will consider only the parallel type here, as that is by far the best known (and the type discussed in ANKS).
As noted in ANKS, even these simplest of CA (1D, B/W, 3-point) are capable of generating very complicated behavior. We emphasize that for finite CA, which are also the only ones that can be simulated on computers, all behavior is eventually periodic since the space (the circle) has finitely many cells (say m ) and that leads to a finite number of possible configurations or states (all 2^m possible strings of 0's and 1's in the 2-color case). However, even with moderately large m, the period in some cases can be so large as to be undetectable in any computer simulations. For our purpose here, it is not necessary to be too strict about finite vs. infinite.
The usual method (widely used in ANKS) of studying the dynamics of one-dimensional CA is to display the on-cells as black squares on a thin strip and leave the off-cells white. A collection of such "lighted" strips stacked one under the other makes up a space-time diagram of a particular CA from a given initial configuration. In the finite cases, it is customary to cut the circle up and make it a flat line segment with the cells at the two ends viewed as adjacent (periodic boundary conditions). The figure below shows a 3-point CA rule and the first 20 steps of its space-time diagram (the CA equivalent of a time series plot) starting from the initial condition where only the central black cell is on.
These figures were created using the "NKS Explorer," ANKS's optional accompanying software. The strip on top clearly shows how the rule is defined at a point (single square, second row) depending on the on-off pattern one time step earlier, of itself and its two immediate neighbors (three squares, first row). The numbering scheme is based on the on-cells (single black cells in the second row of the top strip): Of the eight possible locations, the squares in locations 2,3,4,6 and 7 (counting from right) are on. Viewing these black squares as 1's in the binary expansion of an integer, that integer is found to be 2+4+8+32+64=110; hence the name "Rule 110."
How simple are "simple" CA? Let us now look at CA from the standpoint of standard dynamics. In standard dynamics one defines a system using mappings of the state space. We saw above that the simplest types of CA are the finite, 3-point, 2-color, one-dimensional CA. For these, the state space is an m-dimensional Boolean lattice of size 2^m if the size of the CA is m. A local rule, 3-point or any other, is specified by a vector mapping of the m-dimensional lattice into itself. While CA rules are convenient for computer programming, they lend themselves less readily to relational formalization. However, for small m there is a way of visualizing CA in terms of the standard theory by "translating" them into equivalent or conjugate mappings on one-dimensional spaces using binary expansions of integers.
For each integer between 0 and 2^m there is a unique binary expansion which is specified as a vector or m-tuple of 0's and 1's. The canonical transformation assigns to each vector a unique integer that is given through its binary representation. This transformation is one-to-one and onto, and thus a conjugacey or equivalence between the vector map on the discrete m-dimensional Boolean lattice and the finite sequence of integers from 0 to 2^m on the real line. Through this transformation we can translate any finite CA into a standard dynamical system in one dimension. Because linear neighborhoods are scrambled by the canonical conjugacy, local rules (3-point, etc) do not generally admit simple verbal descriptions in the new context (here is where the higher dimensionality of the state space asserts itself). Nevertheless, since we are only concerned with integers, a digitial computer can easily and accurately plot graphs for these one-dimensional equivalents of finite CA.
The graph below shows what CA Rule 110 (mentioned above) looks like as a standard, one-dimensional dynamical system:
This graph was generated by MathCad Professional 2001. The actual graph consists of the points only (each encircled); the lines joining them are added for ease of visualization. The graph shows how the local CA110 rule - shown as f(n) - maps each state into another. Here the size of the CA is 7 so there are only 128 possible states - a rather insignificant CA by ANKS's standards. Yet, compared with the familiar unimodal maps such as the "logistic map" ax(1-x) that one sees in introductory dynamics texts, this is quite a complicated mapping! In fact, there isn't even a simple "formula" for it (except of course, indirectly through the canonical conjugacy and the local 3-point rule mentioned above).
The basic features of the above graph (e.g., the self-similarity seen most clearly in the repetitive patterns in the portion of the curve that sits above the dashed identity line) do not change by changing the value of m, although the graph size and details do become exponentially large (hence difficult to plot) with increasing values of m. Plotting these large graphs into a bounded area requires inward reduction to the extent that the graphs appear fractal, like a Cantor function. The graphs below show two views of CA110 for m =13 which highlight the self-similarities that exist in the mapping:
In the version below only the points are retained and the line segments joining them have been dropped:
Any finite CA rule, including multiple colored ones, can in principle be translated into a standard dynamical system and plotted like the CA110 above. Other CA rules, even those that generate simple behavior according to ANKS may still have complicated graphs like the ones above (although there are some uninteresting CA which are simple even in the formal sense here). Although values of m for which the above graphs are useful are too small to be of much practical value, the graphs do raise one intriguing question. In ANKS, Wolfram wondered about how some simple CA are capable of generating complex dynamics; looking at their standard-dynamic diagrams I actually wonder how is it that most CA rules end up generating simple dynamics? Could there be a theorem in this?
Wolfram's four classes. By complex dynamics here I mean ANKS-type "Class 4" complexity. I will soon discuss a system that generates a sort of behavior that is complex in this computational sense, yet it is totally amenable to rigorous mathematical analysis. But first, here is a quick look at Wolfram's classification.
Back in the 1980's Wolfram defined 4 classes of behavior types into which he felt dynamic systems like CA would fit; he uses this same classification in ANKS even more broadly. Let me call them W-classes 1-4. W-class 1 consists of systems that generate eventually constant or "uniform" behavior, such as convergence to an equilibrium. W-class 2 includes systems that exhibit "repetative behavior" like nesting and periodicity and other "easily" determined (usually in terms of visualization) types of patterns; in ANKS, CA90 is classified as this type of system. W-class 3 consists of systems (such as CA30) that exhibit random and chaotic behavior. In ANKS we read that most one-dimensional, 2-color CA fall into these three W-classes. But there are also systems (such as CA110) that seem to fall somewhere in between W-class 2 and W-class 3, because there is both some structure and a good deal of unpredictability in their space-time diagrams. These types of systems are said to belong to W-class 4. ANKS goes on to propose this four-class classification for all dynamical systems (this is what I consider to be over-reaching, even if the aforementioned classes had been unambiguously defined).
The CA Rule 110 (inifinte case) has been shown to be "universal" or equivalent to a Turing machine (the basic idea behind the proof is discussed in ANKS; also see [3] for a history of how this came about). What this means for our purposes here is that the behavior of CA110 trajectories are computationally complex and contain no repetitive patterns. This should not be surprizing to anyone who has looked at the many diagrams in ANKS showing the remarkable complexity of CA110 space-time trajectories with localized structures (collections of on-cells) "moving" back and forth through the discrete space (the line of all cells) and appearing and disappearing through "collisions" in unpredictable ways as time moves forward. The next figure for example shows the first 500 iterations (or updates) of the CA110 rule starting with the initial condition where only the central black cell is on (the empty right half of the grid is not shown).
The point of all the discussion in ANKS surronding CA110 appears to be this: The universality of CA110 implies that the behavior that it generates is so complicated that it cannot be modelled or fully described by means of rigorous analysis. Wolfram goes on to suggest that this sort of complexity lies behind all phenomena, human or natural, that are not "obviously simple."
But does all this mean that "true" complexity, computational or otherwise, is beyond the reach of rigorous analysis? Must we give up the quest for true understanding of various scientific and mathematical phenomena because they either appear to be random or because they are way too complicated in the sense of W-class 4 or universality? I am less clear about what we can and cannot rigorously understand than Wolfram is; while we may or may not be able to fully describe the evolution of CA110 by formulas or other relational means, we can succeed that way rather admirably with other types of W-class 4 systems. To make my point more forcefully, I discuss next a variation on a well-known example from elementary dynamics that could only be characterized as W-class 4 in Wolfram's classification, yet its evolution and characteristics are fully understood through rigorous analysis. Also like CA its output appears in one dimension, but unlike CA my example is only two-dimensional.
A simple rule that generates W-class 4 dynamics but admits full description. Consider a non-autonomous (i.e., variable coefficient) logistic equation
X_(n+1) = [A_(n/m) X_n (1- X_n)]
where the states X_n at each iteration n are confined to the unit interval [0,1] and are computed in finite digit arithmetic, retaining only p significant digits (as signified by the brackets [...]). Hence, we may view the unit interval as a row of 10^p cells. Next, with m an integer not exceeding 10^p, I use the coefficient A_(n/m) as a time index for a dynamical system in the following sense: To keep things confined to the unit interval and to eliminate uninteresting behavior, I limit A_(n/m) to the "time interval" T = [3.5,4]. Then divide up T into k equal segments (or time units) and assume that A_(n/m) is constant for all values of n for which the ratio n/m is not an integer; the constant value of A_(n/m) while n builds up to the next multiple of m is considered "an instant" and it is equal to the value of A_(n/m) when n/m was last an integer. Starting at A_(n/m) = 3.5, A_(n/m) increases linearly at a rate of 1/(2k) as n moves past each multiple of m:
A_(0/m) = A_0 = 3.5
A_(m/m) = A_1 = A_0 +1/(2k)
A_(2m/m) = A_2 = A_1 +1/(2k) = A_0 +2/(2k)
A_(3m/m) = A_3 = A_2 +1/(2k) = A_0 +3/(2k)
...
A_(km/m) = A_k = A_0 +k/(2k) = 4.
We may assume here that the precision value p is large enough that 1/2k is not chopped down to zero; also by choosing k appropriately, e.g., a power of 10, we may ensure that no digits in 1/2k are lost in the chopping process.
While A_(n/m) is constant, the logistic equation above generates m states X_n in the unit interval. From a maximum possible of 10^p, these m states may be assumed to be simultaneously "on" in the k-th time instant during which A_(n/m) is constant. This produces a cellular automata-like situation in which all cells are updated in parallel, with at most m states on, at each of the k instants. When A_(n/m) changes, the 10^p cells are updated based on the states generated by the logistic with the new value of A_(n/m). Note that in principle the parameter values p, m, k can be as large as we please, so the time limit A_k = 4 can be as far away as desired.
The next figure shows the evolution of this type of automaton in time indexed by A_(n/m) for certain values of of the above mentioned parameters p, m, k. The initial configuration is the set of distinct states generated by the logistic equation at time A_(n/m) = 3.5 from some seed value X_0.
As we see in the above graph, localized structures appear and they multiply to a large number of branches by the time A_(n/m) = 3.58. As we continue on to A_(n/m) = 3.6, we observe that some of the branches get thicker and start merging together. We also notice "windows" where the number of on-cells (distinct states X_n ) is few; one such window appears shortly after A_(n/m) = 3.58. Also note that the rows towards the bottom of the figure seem to contain a large number of on-cells in no obvious pattern beyond their clustering.
In the next diagram, we reach A_(n/m) = 3.7. Here we notice at least two major events: The merging of all branches and the appearance of a sizable window where there appear to be as few as 6 on-cells. Note that although the logistic equation generates all the states seen so far, there is no obvious hint in that very simple rule as to why all this structure should exist.
Continuing to A_(n/m) = 3.8 in the next diagram we not only see another major window (distinguished by 5 cells) but we begin to notice curve-like patterns going from top to bottom in the space-time diagram along which there appears to be a greater density of on-states. Can there be any more surprizes when we go to A_(n/m) = 3.9?
In the next figure where we reach A_(n/m) = 3.9 there is yet another window, the largest yet, characterized by 3 on-cells that eventually multiply into large numbers of on-cells in later stages.
The automaton-like dynamical system described above is evidently a W-class 4 system. The time period for its evolution can be made larger simply by increasing the parameter values p, m, k. Doing so will reveal more intricate "in-between" structure (e.g., more windows and downward cascades) that we do not see in the above diagrams due to the coarseness of time and space. Furthermore, as the next figure shows through a magnification of a portion of the preceding figure, the highly complex patterns of on-cells in most time instants do not appear to be repetitive or otherwise simple.
The following points should be emphasized:
1. The logistic rule that generates the above dynamics is a simple rule, much like CA rules; for each n, we simply multiply the three numbers A_(n/m) , X_n , 1- X_n and chop off digits beyond p in order to get the next state X_(n+1).
2. The dynamical system is two-dimensional (because of the variable coefficient A_(n/m) ) with a one-dimensional output, unlike CA systems which can have arbitrarily large dimension (equal to the number of their cells) even if their output is one-dimensional.
3. The simple computational rule behind the above diagrams does not offer any obvious clues about the details of the complex structure that it generates any more than CA110 does about the sturctures that appear in its trajectory.
In spite of all of the above, the essential aspects of the structure generated by the logistic automata system above is fully understood through rigorous qualitative analysis! The space-time diagrams above are similar to the bifurcation diagram of the ordinary logistic equation. Of course, they are not the same because of the finite-digit arithmetic and a finite number of iterations. However, it is to be noted that the larger the parameter values p, m, k, the closer the situation is to the logisitc's bifurcations on the real line. Therefore, we can say with confidence that we fully understand the complex logistic system discussed above, because we fully understand the essential features of the bifurcation diagram of the logistic and similar maps of the line.
Here is a brief explanation of the sturctures seen in the logistic diagrams: The windows correspond to periodic solutions that occur as a result of tangent bifurcations, and the downward cascades are the results of period-doubling bifurcations - all in the peculiar fashion determined by the Sharkovski ordering. The changing patterns on the horizontal lines (on-cells at time k) proceed from periodic to the mildly aperiodic (or almost periodic or quasi-periodic) trajectories near the top of the time scale to nearly random or chaotic as we move farther down. Quasi-periodicity typically follows a period-doubling cascade for increasingly shorter times as we descend towards the bottom; chaotic behavior typically follows for increasingly longer times until it is interrupted by a tangent bifurcation. The curves that oscillate from top to bottom are polynomials associated with the critical point of the logistic map; the higher density of points (or on-cells) near these curves is therefore explained by the attracting nature of the critical point according to well-known theory. There are complete descriptions supported by rigorous proofs of practically all that we see in the bifurcation diagram of the logistic map and similar unimodal functions; for some of these details and an extensive list of references, see Chapter 2 and the bibliography in [5].
In the absence of the established theory the dynamical system shown in the above pictures might seem as inexplicable as the space-time diagrams of CA110. By increasing the parameter values p, m, k we could go on and on generating more configurations only to find more patterns, some repetative and some not; we would see patterns moving around on the line, splitting and then merging in a variety of different ways. In particular, it is fair to speculate that the Sharkovski ordering of periodic patterns might defy guess work based on simulations, especially because finite precision p would mask certain larger periods or make aperiodic solutions seem periodic. To get a better (i.e., more mystifying) picture, consider repeating the above experiment not with the logisitc map, but with a more complex second-order nonlinear difference equation (this would increase the system's dimension to 3 but still plot points on a line - click here for an example that is presented similarly to the logistic above). Although there are significant differences between these types of systems and the CA110-type automata, many of the points that are made in ANKS about computational complexity can also be made about our difference equations systems as well.
Conclusion. Nowadays, it has become commonplace in scientific disciplines such as the life sciences and the social sciences to use computer simulations, clever algorithms and so forth to solve problems. These approaches have generated a lot of facts and many interesting questions, but they have yielded little understanding of the mechanisms that produce the simulated/data-mined/eyeballed outcome. These approaches are popular because they enable one to make conjectures and then offer computational "evidence" of possible validity. This is generally the first phase of modeling, but we often see little that goes beyond conclusions reached using human intuition applied directly to observations of patterns, numbers or shapes. Increasingly, the second or analytical phase of modeling is being discarded and there seems to be little concern for why things are the way they are. While reading ANKS, I got the feeling that it may be more representative of the mood of the times than a resolution of some problem.
The questions answered by Sharkovski's theorem and similar results, might have been left open if we had relied only on the digital computer for insights. Crude bifurcation diagrams generated by computers back in the 1960's probably motivated the investigation that led to the conclusions discussed above. But perhaps it was fortunate that capable digital computers of today were not in wide circulation back in the 1960's and 70's. Sharkovski's theorem and many other deep results about maps of the line are not valid for maps of higher dimensional spaces - here is a significant difference in the level of complexity that does not show up in the PCE equivalence class. But the successes that we had with dimension 1 (including with the homeomorphisms of the circle) should provide the motivation to try new and varied approaches for dimensions 2 and higher. If we choose to be impatient and content with computer simulations and what our eyeballs tell us about them, then it is likely that we will never rise up to the challenge; indeed, it seems that from the standpoint of the principle of computational equivalence there is no difference between complex behavior in dimension 1 and those in higher dimensions, as long as they are all W-class 4. We have shown here that this is not the case.
It is certainly difficult to gain deep knowledge about large or high-dimensional systems; for example, even for one-dimensional maps, the proof of Sharkovski's theorem and results of a similar nature are long and complex, rivaling universality proofs in length and intricacy (see [5] for details and for other references). Further, I am by no means suggesting that we abandon the computational/statistical procedures that are especially in vogue now; far from it, we need these methods to help us model large-scale, open systems (e.g., the weather, the evolution of spices...) which are not immune to random interference from the environment at random times. What I am suggesting is that the computational/statistical methods alone do not teach us much about anything; by their very natures, they can only be used to "support" conjectures or verify claims, if true (remember that it was not a lack of creativity or computational resourcefulness but modern algebraic theory that finally stopped hopeful people from trying to square circles or trisect angles with just a compass and a straight-edge). Even the proof of the "4-color Theorem" back in the 1970's which was made possible by the availibility of greater computational resources was first of all a proof: A complex relational construct made of chains of arguments flowing from hypostheses to conclusions.
Our theoretical understanding of higher dimensional systems is simply far from being adequate at this time, but the past has shown that remarkable things are possible with persistence. To site another example, recently Fermat's Last Theorem was proved using algebraic topology methods. This problem had been approached using numerical and algorithmic methods which offered plenty of evidence that it was probably true, but no clue as to why. Only now we are beginning to understand what that problem really was about. More to the point, the pre-computer-age efforts to resolve Fermat resulted in good mathematics that has survived and flourished to this day, but the more recent and less revealing numerical/algorithmic results are largely forgotten.
Hassan Sedaghat
April 6, 2003
References:
[1] Stephen Wolfram, A New Kind of Science, Wolfram Media Inc. (2002)
[2] Steven G. Krantz, "A new kind of science by Stephen Wolfram," (book review) Bulletin of the American Mathematical Society, 40, p.143, 2003.
[3] Lawrence Gray, "A mathematician looks at Wolfram's new kind of science," Notices of the American Mathematical Society, 50, p. 200, 2003.
[4] Stephen Wolfram, Cellular Automata and Complexity: Collected Papers, Addison Wesley (1984) Also see Wolfram's Publications on the web
[5] Hassan Sedaghat, Nonlinear Difference Equations: Theory with Applications to Social Science Models, Kluwer (2003)
Take a look at the book Nonlinear Difference Equations
Care to try your luck with a few outstanding problems of mathematics and mathematical physics? Take a look at the million-dollar ones showcased by the Clay Mathematics Institute!