| Before Stephen Wolfram's work in the early nineteen-eighties, research on cellular automata was generally done by studying variations produced by a single automaton. John von Neumann created the first cellular automaton in the late forties, based to some degree on work by Stanislaw Ulam. Much later, John Conway's Life automaton became quite famous in mathematics, and was studied extensively in the sixties and seventies. Both of these researchers worked first on creating the rules that would define an "interesting" automaton, then studied the patterns that could be generated with it.
Wolfram's breakthrough was to enumerate an entire subclass of the rules an automaton might use, and compare execution based on each. Instead of studying one automaton in great depth, he studied many at once -- experimental mathematics, if you will. Wolfram's research implemented a given rule, then watched the evolution of the automaton using it with a beginning pattern which was kept constant. On each experiment the rules were changed but the seed was not, so an overall classification of automata became apparent when the resulting outputs were compared. For an example of the type of automata he considered and the rules governing their behavior, see my writeup under one-dimensional cellular automaton.
What Wolfram found was that rules could produce one of four distinct types of behavior. He published these findings, suggesting that they be ordered from least to most "interesting." This might seem somewhat arbitrary, but should become clear after reading about each type. His classes are:
- Class 1: Homogeneous state. Automata following class 1 rules die back completely after few or no steps of evolution. There is no initial configuration of sites which produces patterns of any length using these rules, it will always evolve to a homogeneous state. In a 1dCA this looks like one or two steps of noise, then a blank field.These are non-reversible, because once the field is blank no previous state information can be derived.
- Class 2: Simple stable or periodic structures. In these automata, self-contained structures can exist that will not terminate in any number of time steps. Another way of putting this is that the information (the importance of a its value) of a site can only propagate a finite distance, and thus cannot affect distant structures regardless of time. This acts almost as a "filter" on the initial configuration, choosing some features to propagate over infinite time steps, and some to remove completely. For a 1dCA this may look like solid bars over time on the automaton, or train tracks, stair steps, etc. Non-reversiblejust like class 1, since the fixed structures give no information about the initial state which was lost during evolution.
- Class 3: Chaotic pattern. This is where cellular automata start to get interesting. In these, predicting the value a site will take requires knowledge of the current sites, just as in a class 2. In the class 3, the amount of current knowledge needed grows as one tries to predict further into the future -- hence it is a chaotic system. As with all well-defined chaotic systems, a given state is completely reversible; the previous state (and all the ones before) can be predicted by examining the current state. This class of automata is non-deterministic in that to find the value of a site after an infinite amount of time, an infinite number of initial conditions must be considered.
In a 1dCA, class 3 automata look terrifically interesting, sort of like the coloration on a cowry shell or the pattern of scales on a fish. It should be noted that while this class of behavior is chaotic, it is not random. That is, large scale structures can evolve during evolution, and be identified as such; these automata do not generate undifferentiated noise. One variation of class 3 behavior can be seen in my writeup under 1dCA.
- Class 4: Long-lived, complex structures. Instead of site information propagating outwards at a constant speed, these automata propagate site information at variable speeds, depending on the structures themselves. Class 4 automata are the only non-trivial (i.e. have complex behavior rather than the class 1 steady state) non-reversible automata; since the current site values could have arisen from more than one previous configuration, current site values cannot be extrapolated backwards to know previous configurations. Finding the value of a given site a certain number of steps in the future is an intractable problem; except for special cases, it cannot be found without actually doing all the drawn-out computation.Conway's Life is a class 4 cellular automaton.
The upshot of this insane complexity is that any class 4 automaton can be considered a universal computer. Given the right initial conditions and a finite number of time steps, any computable problem can be solved by it. That number of time steps is unpredictable except in specific cases because of the Halting Problem, which should be familiar to anyone with background in Computer Science. Not only is use as a universal computer of theoretical interest; there has been suggestion of constructing a class 4 automaton on silicon which could have billions of sites and do millions of time steps per second. If constructed, programming this device could provide interesting work in Computer Science for the next fifty years.
1dCA representations of class 4 automata are, unsurprisingly, striking to observe. A somewhat close description might be of coral, where some areas are flat while others grow and branch out in seemingly (but not truly) random patterns. These automata seem to me to always look quite organic, and I hope to have a poster of one some day.
|
