The evolution of an automaton is nicely represented by a transition diagram or graph; every configuration is represented by a node, the nodes are linked according to the rule of evolution. Chains formed from the links describe long term evolution. The deterministic character of evolution implies that there is exactly one outgoing link for each node. In the forward direction, chains must close into loops; they could also continue indefinitely when the number of configurations is infinite.
In the backward direction the additional possibility exists that a configuration has no ancestor. For a finite diagram that is a necessary alternative if any of the chains are confluent. The reason is simply that after counting exactly one link per node in the outgoing direction, a node with two incoming links must deprive some other node of a compensating incoming link.
Simple counting does not work for infinite diagrams, but the fact that the neighborhoods defining the evolution have to overlap to some degree allowed Edward F. Moore[51] to show that a similar conclusion nevertheless follows, namely that whenever some configurations have multiple ancestors, there must be others which have none; the term Garden of Eden seemed appropriate to describe the situation.
The result is an interesting limitation on the kind of constructions which an automaton can perform. But a universal constructor is not expected to construct everything, and according to this theorem, clearly cannot. Generally it is considered adequate that it can construct objects at least as complicated as a Turing machine, or slightly more so, so as to be able to make copies of itself.
There are straightforward procedures for ascertaining the Garden of Eden configurations of a one dimensional automaton, as well as the actual ancestors for the remaining configurations. Jen[43] has shown one such construction, based on a symbolic de Bruijn diagram. It is typical that the corresponding calculations are undecidable for arbitrary two dimensional automata or beyond, generally because of conflicts arising from the Post correspondence principle. Nevertheless two Garden of Eden configurations for Life have been published [29, page 248,],[9, page 829,], and a third cited[29, page 248,], all of them were evidently encountered after a long series of exhaustive eliminations.
Garden of Eden configurations represent one end of the evolutionary tree, its leaves, which lie at the opposite extreme from the cycles, which form its roots. Discovering them requires more than simply following out trial evolutions, but their inclusion nevertheless forms an interesting part of the description of any given automaton.