next up previous contents
Next: One dimensional automata Up: History Previous: The Gardner era

The Wolfram era

Professional scientific interest in cellular automata received a considerable impetus from the investigations of Stephen Wolfram [118], who undertook a computer based search through the properties of one dimensional automata, guided by some concepts from the realm of nonlinear dynamics and statistical mechanics. For anyone, in fact, the microcomputers, programming languages, and video displays which are currently available are sufficient for many experimental studies of cellular automata, not a few of whose results have considerable artistic merit.

A recent article exploring the aesthetic side of automata theory was entitled Abstract Mathematical Art, by Kenneth E. Perry [95], published in the December, 1986, issue of Byte. The article included a Basic program for use on IBM/PC compatible computers, with indications that a Pascal version was available from the magazine, and a statement that the author himself had used machine language to quickly seek out the hundred examples which he selected for the readers' experimentation. Several of them were shown in striking color photographs illustrating the article.

The idea of a one dimensional cellular automaton is quite simple, and its evolution in time is ideal for a two dimensional presentation, as on a video screen. To start with, a cell is a region, even a point, with differing forms, called states. For convenience, these states are usually numbered with small integers beginning with zero, rather than described. For the purposes of automata theory the nature of the states does not matter, only their relation to one another, and the way they change with time according to their environment. Since they are abstract, they can just as well be represented by colored dots on a video screen, which is what makes them so dramatic when interpreted as an abstract artistic design.

Although both von Neumann and Conway were aware that alternative rules of evolution existed, incredibly large numbers of them in fact, they concentrated on one single rule which served their purposes, exploring its consequences in detail. Wolfram, by contrast, was one of the first to compare the evolutionary histories of large numbers of different rules, with the intent of classifying them according to their long term behavior. Indeed he seems to have been inspired by work in dynamical systems theory, particularly Stephen Smale's discovery of ``strange attractors,'' and the possible parallels they might have in automata theory.

In any event, he noticed that the evolutionary histories of linear cellular automata were quite varied, for which he proposed four classes. The first contained automata evolved automata evolving, usually fairly rapidly, into a constant field. Quiescence, of course, was a basic assumption of von Neumann, Conway, and others who needed a static background against which to perform their constructions. Wolfram took this class to be the analogue of those dynamical systems which evolve toward a point of stable equilibrium.

The second class was supposed to correspond to the limit cycles of nonlinear mechanics, that is, limiting behavior which is cyclic. With automata, many limiting fields are not quiescent, but nevertheless show little, no, or completely predictable, activity. Life 's still lifes are a typical example, as are the blinkersblinker, gliders, and other isolated periodic structures which characterize its long term evolution.

The third class is quite the opposite, consisting of chaotic fields whose behavior is never predictable; these would correspond to ergodic behavior in dynamical theory or even strange attractors.

The fourth, and remaining, class is the one which may be the most interesting; Wolfram wished to associate it with universal computation, but it is essentially the same class which held Conway's interest; the reasoning was quite similar. In spite of the ordering implied by Wolfram's numbering, the fourth class is probably best regarded as an interface between the second and third classes as suggested by Christopher Langton [71]. In any event, it is a class characterized by ``islands of chaotic behavior in an ocean of quiescence.'' One does not find such behavior in binary automata of small radius; it is always fairly uncommon, yet far from rare.



next up previous contents
Next: One dimensional automata Up: History Previous: The Gardner era



Harold V. McIntosh
E-mail:mcintosh@servidor.unam.mx