Cellular Automata have been studied as a part of the abstract theory of computation since the time that John von Neumann became interested in the possibility of constructing self-reproducing automatic factories. Since actual factories and physical machinery involve a myriad of practical but non-essential details, he eventually followed a suggestion of Stanislaw Ulam that an abstract mathematical model would be more amenable to a demonstration of the possibilities of universal construction and self reproduction. He worked out a scheme for such an automaton, in terms of a cellular space occupying a two dimensional grid, in which each cell would be found in one of twenty nine states.
The details of von Neumann's construction remained unpublished at the time of his death in 1957, but were subsequently edited and published by A. W. Burks [90]. Even as he was working on his model, von Neumann realized that it was too literal an interpretation of the computing machines of the era, but he himself never attempted to carry out a complete revision of his original design. About a decade later, in the years 1964-65, E. F. Codd [25] worked out a variant which required only eight states per cell, still using the original five cell neighborhood.
Ulam's [111] work on functional iteration and his experiments on nonlinear mappings were reported in conference proceedings, and in the course of time cellular automata became a topic in the theory of abstract machines, along with the work of Edward F. Moore , Claude Shannon , and others. The principal results of the time were the demonstrations of the existence of universal constructors, and Moore's ``Garden of Eden'' theorem which showed the necessary existence of configurations in automata of a rather representative type which could only be initial states. Such a pattern could never again be repeated during the course of the automaton's evolution.
Of course, there were even earlier beginnings to automata theory, for example in the studies of Warren S. McCulloch and Walter Pitts in 1943 on neural nets, followed in 1951 by an interesting mathematical abstraction to regular events by S. C. Kleene , and even in general ideas about the new subject of Cybernetics introduced by Norbert Wiener [115] in his famous book of 1948.
An interesting parallel development arose from an even older source, Henri Poincaré's emphasis of the qualitative aspects of classical mechanics in terms of stability, ergodic properties, and the recurrence of orbits; such topics nowadays constitute measure theory, topology, or symbolic dynamics, all of which are an outgrowth of various of Poincaré's ideas.
The latter, symbolic dynamics, elaborated by George Birkhoff [15] and others, was described by Walter Gottschalk and Gustav A. Hedlund in an American Mathematical Society Colloquium Publication [45] in 1959, and continues to be a subject of intense mathematical interest. Hedlund's very abstract summary [56] of 1969 contains a wealth of results applicable to cellular automata, although its orientation is entirely different and the relationship between the two concepts has not always been well appreciated.