Supposing that von Neumann's goal of exhibiting an automaton capable of universal construction or of universal computation has been realized, additional questions come to mind. For example, an automaton which contains an embedded Turing machine has to suffer some of the same limitations as the Turing machine, the most notorious of which is undecidability.
It would appear that a cellular automaton ought to be more versatile than a Turing machine; for example it could have numerous read heads and work on many computations simultaneously. Nevertheless, since any automaton can presumably be modelled within some Turing machine, the computational powers of the two artifacts must be coextensive. One seeming paradox arose when it was found that some automata had configurations which could not be the product of any evolution, the ``Garden of Eden'' states of Edward F. Moore [82,84].
The reconciliation of such states with a universal constructor lies in the realization that the constructor is not required to fill space with arbitrary designs, but rather to create specific objects (including copies of itself) according to the instructions which it has received. Universality refers to whether arbitrary descriptions can be followed, not whether arbitrary constructs can be produced.
Nevertheless, there has been considerable interest in ascertaining whether or not there are restrictions on the long term behavior of an automaton, both in the remote past and in the remote future. Such restrictions could manifest themselves in unattainable configurations such as the Garden of Eden, as well as in certain limiting configurations which would only develop fully as limits.
But there is also a middle ground, consisting of rules or even of configurations within a given rule, which never end up in some inaccessible region, either past or future. For this to be true, it is especially important that there be no barrier such as the Garden of Eden, devoid of a previous existence in any form. Equally, although the future always exists in some form or other, there might be reasons to avoid an approach to extremely complicated limits.
In other words, there is an interest in time reversal symmetry, or even a simple equivalence between past and future, whereby past configurations would be just as recoverable from a given configuration as the future configurations that are deducible from the same data. Quite trivial instances in which the states shift sideways, remain unchanged, or complement themselves between generations readily come to mind; naturally real interest centers on whether there are others, besides.
S. Amoroso and Y. N. Patt [4]
searched for possible reversible rules and discovered eight nontrivial
rules in 1972; Tommaso Toffoli [109] found a way to generate whole classes by an increase in dimension
in 1977, and Edward Fredkin discovered another scheme which has been
reported in Toffoli and Margolis's book [110]. Fredkin employed
evolutionary functions extending over two generations, evidently
extendible within the same framework to three or more generations. Yet
another alternative employs some of the states in a cartesian product
to create a sort of memory.
It is interesting to observe that the whole idea of reversible automata falls within the province of dynamical systems (once the connection is realized) just as it was already reported in great detail by Hedlund [56] in 1969. A recent survey article by Roy Adler and Leopold Flatto [2] contains a good exposition of the relationship of symbolic dynamics to flows through a graph.
The reason that symbolic dynamics has such a special relationship to reversible automata lies in the fact that a dynamical system can be given a topology, with respect to which it is much easier to discuss infinite systems and the existence of limits. This in turn brings up such concepts as continuity, the multiple valuedness of mappings, and the existence of inverse functions.
An essential element of the discussion hinges upon the fact that the evolution function for automata is not invertible in and of itself, but the discrepancies between counterimages can be pushed to remote regions of the automaton. With the help of the topology they can then be made to vanish in the limit, providing a context in which the reversibility of evolution can be discussed.