Introduction
When John von Neumann [1] worked out the theory of universal constructors within the framework of cellular automata in the mid fifties, philosophical questions soon arose concerning ancestorless patterns, which surely could not be ``constructed'' through the intermediary of other configurations occupying the same system. That such predicaments could arise under certain circumstances was first appreciated by Edward F. Moore [2], whose article of 1962 was reprinted in a collection of influential papers edited by Arthur W. Burks [3] in 1970. Even though the only requirement which von Neumann was interested in satisfying was that a device with the computational power of a Turing machine should be capable of producing copies of itself --- not necessarily that it had to fill space with arbitrary designs --- the latter concept is an interesting one which has received further study.
In short order the question turned into the relationship between the local mapping in an automaton, which assigns successors to neighborhoods, and the global mapping, which produces the succession of configurations from one generation to the next. In contemporary mathematical terms, the interesting questions are whether the global mapping is injective, formerly called one-to-one, and also whether it is surjective, formerly designated onto. In the latter case every configuration has at least one ancestor, and there is no Garden of Eden. For finite sets the equivalence of the two characteristics follows from counting arguments which no longer apply to infinite sets.
To pose the problem properly for infinite automata, some thought has to be given to the meaning of infinity, often with respect to boundary conditions which are relaxed or assumed to lose their influence as the automaton grows in size. Three choices usually considered are: 1) cyclic boundary conditions, 2) quiescence at infinity, or 3) a quite general, unspecified arrangement (sometimes with a topology which minimizes the importance of exceedingly remote cells).
In a sense, these are external considerations, subordinate to other, internal, aspects of the problem. Fundamental to the nature of cellular automata is the difference in size between cells and the neighborhoods which determine their evolution, resulting in a permanent discrepancy between the area of a region and that from which it has evolved. Paying attention to the external aspects may try to avoid the difficulty by folding or smoothing the margins, but it is probably better to resolve the internal aspects first, adjusting them to the external requirements at the end.
Although it is quite easy to work out ancestral neighborhoods for one or even a few cells, problems of consistency are bound to arise because the neighborhoods always overlap. Fortunately, especially in one dimension, there are matricial techniques based on the de Bruijn diagram which organize the relationships involved, and the calculation of ancestors can proceed. Most commonly inconsistencies arise which cannot be resolved, leading to the Garden of Eden, and the conclusion that most rules of evolution are not surjective. For such rules, most configurations have multiple ancestors whilst others have none.
Among the exceptions, the freedom of choice which exists in the margin usually leads not just to a single ancestor for each configuration, but to several distinct ancestors. But for a still smaller subset of rules, the freedom is to greater or lesser degree illusory, even to the extent that the state of one of the cells in the ancestral neighborhood --- the central cell, for instance --- can be deduced once the state of the evolved cell and some of its neighbors is known. The rule of association can be used to run the automaton backward, for which such an automaton would be called reversible.
Historically, various attempts were made to define the problem, and to encounter examples of various types of behavior; some of the conflicts inherent in which were discussed by Sven Skyum [4] in a 1975 article aptly titled ``Confusion in the Garden of Eden.''
Interestingly, similar studies had grown out of the topic of symbolic dynamics and ergodic theory, originating with Henri Poincaré in the nineteenth century, continued in the first half of the twentieth by George Birkhoff [5], formalized by Walter Gottschalk and Gustav A. Hedlund [6] in a 1955 Colloquium Publication of the American Mathematical Society. In 1969 Hedlund [7] published a thorough summary of the properties of automorphisms and endomorphisms of the shift dynamical system, albeit written in a very terse mathematical language with many topological features.
Indeed, continuous mappings of the shift are cellular automata, providing one of the few known instances of an unequivocal application of the theory of cellular automata to another field; ironically the applications to symbolic dynamics and ergodic theory were worked out in exhaustive detail much before the subject of cellular automata became particularly organized, and quite unbeknownst to the majority of its practitioners.
In 1978, about a decade after Hedlund's fundamental paper, Masakazu Nasu [8] undertook to describe these results with the aid of graph theory, without relying on topology, and incorporating some ideas from automata theory. During this same period a variety of other articles appeared; but in the meantime, a more direct approach to the explicit construction of reversible automata was invented, then applied to some physical problems, by Edward Fredkin, Tommaso Toffoli, and others.
Recent interest in automata has been greatly stimulated by Stephen Wolfram's computer
experiments, first reported in Reviews of Modern Physics [9] in 1983; familiarity with his reprint collection [10] of 1986 is assumed, as well as his use of 
whenever k-state cells form a neighborhood of
radius r (possibly half-integral) is followed, likewise his k-ary
enumeration of evolutionary rules.
This paper also relies heavily on the properties of nonnegative matrices, an exposition of whose theory can be found in half a dozen or more contemporary textbooks, such as Gantmacher [11], Bellman [12], Varga [13], Seneta [14], Berman and Plemmons [15], or Minc [16].
Harold V. McIntosh
E-mail:mcintosh@servidor.unam.mx