next up previous contents
Next: The Wolfram era Up: History Previous: Automata theory

The Gardner era

Public awareness of cellular automata can mostly be attributed to John Conway's interest in finding a simpler configuration than von Neumann's and exploring its capabilities. Some of his results were presented in 1970 as an ecological game called Life , at a time when such concerns were popular, in Martin Gardner's monthly Mathematical Games column in Scientific American. For a period of about three years Robert T. Wainwright maintained a quarterly newsletter [113] disseminating discoveries made by Martin Gardner's readers, some of which were followed up in later columns in Scientific American. Many of the more interesting results were obtained at MIT's Artificial Intelligence Laboratory with the help of the graphics facilities of their PDP-6 computer gif.

When microcomputers began to attract popular attention, Conway's game of Life became one of the early inspirations for an application; Cromemco's ``Dazzler,'' a color video controller and one of the earliest peripherals, was frequently used to display the evolution of Life configurations. Early issues of Byte magazine contained some material on Life , but in one memorable issue many results which had appeared in Wainwright's newsletter [113] a decade earlier, but still not reached mass circulation, were presented by some of their discoverers. Other magazines, such as Omni, also revived the topic [53,85], and in recent years Scientific American has returned to the subject, most recently in A. K. Dewdney's Computer Recreations, the current successor to Martin Gardner's column.

All of Martin Gardner's columns of the early 1970's have been reissued in a recent reprint collection [43], together with some of his reminiscences. He identifies three places as having been particularly active centers of interest, at all of which people were mainly concerned with collecting examples of one type of behavior or other, many of them reported in Wainwright's newsletter. Many fanciful names were invented to describe the variety of configurations which were found, including two (glider gunglider gun and puffer trainpuffer train) due to Conway himself.

Conway had devised the rules of evolution of Life carefully, to avoid the extremes in which live cells proliferated and grew without bound, or in which live cells dwindled and eventually died. He was still not sure about the ultimate fate of his delicately balanced creation; there could always be some fairly uncommon combinations nevertheless capable of unlimited growth. Several small patterns were known which delayed thousands of generations before their final behaviour became evident.

A five-cell figure called a ``gliderglider'' capable of diagonal movement had been discovered in the early stages of experimentation, as well as larger figures -- ``space ships'' -- capable of horizontal or vertical movement. An isolated ``glider gun''that produced gliders periodically would be one structure with unlimited growth, a puffer train formed by a space ship which left permanent debris behind as it moved would be another. Whether such structures existed was not clear at first, but it was evident enough that regular structures would be required before theorems could be proved. Otherwise there were simply too many courses of evolution open to study them all.

At MIT glider guns were quickly found; also glider collisions were studied in great detail. Interestingly enough, puffer trains were also found, even some that included gliders in their residues. Through this combination a mass was found which, not really dense but still reasonably compact, violated Conway's conjecture against an infinitely growing configuration in the worst possible way. That is, it occupied a diamond shaped region of constant density whose borders expanded at a uniform velocity -- a quarter of the ``velocity of light'' -- because of the prevalence of gliders in its makeup.

Glider guns created a steady stream of objects - gliders - which could be used as signals in something resembling an electrical network, which enabled Conway to design a configuration which fulfilled von Neumann's original goals of creating self-replicating automata. In the process it was made clear that many questions about automata theory were undecidable because their answers would also have to describe the Turing machines which could be associated with the process. However, that conclusion can be reached much more directly by embedding linear cellular automata which emulate Turing machines in two-dimensional environments. However such machines use many more than the two states per cell which Conway's construction achieves.

Work at MIT also revealed some interesting schemes for constructing very large configurations of period two, even some which completely vanished in the process of creating the new generation and which in turn disappeared as they recreated the original generation. Another group of students in Canada worked out large numbers of oscillators of different periods, on the basis of the strategic placement of structures which came to be called ``eaters.''

It was evident from the first that some structures were much more stable than others, and that they could be used as building blocks to regulate the growth of more erratic or less stable combinations. Indeed, glider guns seem to have been a byproduct of having first constructed oscillators by confining colonies with promising but undisciplined growth, and then checking out collisions of the moving parts of such oscillators.

Of course, given moving objects such as gliders or space ships, it was natural to look into their collisions with stationary objects or with each other. Rather than simply admiring the spectacle, one can take a scientific approach, systematically varying the relative positions of the reactants and recording the results. In one way or another, some extremely varied and highly interesting configurations were discovered.

Wainwright undertook a classification of all the noteworthy Life configurations which his correspondents reported, and one could fairly say that the ``Gardner era'' of cellular automata was characterized by an intensive search for ``interesting'' configurations in Conway's Life . Some modest variants were considered by various persons; but Life itself was sufficiently challenging, and the variations exibited by the variants insufficiently spectacular, to result in any great volume of reports.

The extent of the diverse results which were obtained was indeed impressive, but it was inevitable that the field would become saturated as the readily imaginable concepts of ``interesting'' were explored, and the combinations accessible to the computer technology of the day were exhausted. The next steps depended not only upon a new computer technology, but upon advancing concepts in information theory and even in formal language theory.

next up previous contents
Next: The Wolfram era Up: History Previous: Automata theory

Harold V. McIntosh