The idea of von Neumann was to imitate the behavior of the human brain for constructing a machine able to solve to complex problems [5]. He considered that a machine with such complexity must contain self-control and self-repair mechanisms. His idea was as well to establish differences between processes and data, considering that they are in equality. This drives to find a machine able to self-reproduction.
The first self-reproductive cellular automaton would be proposed by von Neumann evolving in a two-dimensional array, with twenty nine elements as a set of states and evolving with the von Neumann neighborhood. An important problem is the implementation of this model, due to this complexity the von Neumann rule has been partially implemented in a computer in [30] by U. Pesavento.
Von Neumann was successful in finding discrete structures of cells useful to generate new identical structures. Although this result is a very primitive form of life, it is very interesting because usually one hopes that a machine can only construct an object of smaller complexity than itself. With self-reproductive cellular automata we obtain a machine able to create new machines of identical complexity and capacities.
The von Neumann rule has in addition the property of making universal computation, this means that there is an initial configuration of the cellular automaton producing the solution of some algorithm, this property is of theoretical interest and not as much of practical application. Then the property of universal computation means that some computer logic (logic gates) can be simulated by a rule of a cellular automaton. All this demonstrates that the complex and unexpected behavior can emerge from a cellular automaton.
Von Neumann raises the idea of an universal constructor (taken from Barry McMullin [27] and [26]), in a sense which was not properly of computation. For this system he required of a decoder and a description in order to obtain the descendent phenomenon, in addition of requiring a copy of the description adding it as a part of the descendant.
This result is more difficult than demonstrate the existence of a simple self-reproducing machine, in particular it indicates the possibility that arbitrary complex machines are able of self-reproduction and this is what differences the von Neumann result from the one obtained by C. Langton in [19]. The operation of the machine of Langton can be divided in two activities: copy and decoder, because it does not incorporate something like a general constructive automaton.
Exactly self-reproduction is a characteristic of these complex systems, that is, systems which preserve but do not increase their level of complexity in their descendant systems. Von Neumann was interested in seeing exactly the minimum level of necessary organization for self-reproduction. As an index of this minimum complexity, he estimated the minimum size of patterns for the self-reproduction in a cellular space. Then it is possible to design an universal constructor in a rectangular adjustment of
cells, where several of the cells remain in a quiescent state.
The universal constructor concurs in a small part of the pattern for the self-reproduction. The reviewer unit and parts related to manipulation of memory are larger. Many of the patterns are given by the units coding and decoding the transmitted information or the reception of other parts of the pattern. Von Neumann estimated the total size of the patterns for self-reproduction in 200,000 cells, this order can vary depending on the design.
In 1982 Conway realized the penultimate reduction with the automaton The Game of Life, in two dimensions with a set of two states and evolving with the Moore neighborhood. With this automaton it was demonstrated a non-trivial reproduction similar to the von Neumann model. Nevertheless the rule of Conway was not designed to facilitate self-reproduction. The existence of self-reproducing patterns in the automaton of Conway is a strong evidence that the type of self-reproduction imagined by von Neumann is a natural phenomenon, possibly in many contexts [32].
In 1998 the last reduction was made with the demonstration of Cook in a one-dimensional cellular automaton, this automaton known as Rule 110 has two states and evolves in neighborhoods of size three [7].
The concept of universal constructor [26] is developed by Von Neumann, as a preliminary step to introduce the problem of obtaining spontaneous and open growth in the complex behavior of the automata. The concept was formulated as an analogy to the result of Turing and his universal machine.
The investigations made by von Neumann in the theory of complex automata are characterized by the problem of constructing non-trivial self-reproducing machines, where non-trivial is a requirement which means that the machine must have in an enviroment of a universal computer.
McMullin comments two very interesting things distinguishing an universal constructor from an universal machine. The Turing universal machine needs a description of the machine to work out, whereas the universal constructor is able to construct his own description and operate, that is, there are not Turing universal constructors.
Developing and obtaining a complete description of the universal constructor of von Neumann is really a very interesting and complicated task. On the other hand Conway raises an interesting problem in The Game of Life, it consisted of awarding the first person demonstrating a pattern with a constant and unlimited growth [32].
Many attempts were made to find such pattern, one of them was the arcon object formed by seven alive cells. Observing that it has a constant growth in a long term, but it was possible to check that its growth was not unlimited, finding stability in 5206 generations (nevertheless its evolution is very interesting). There were several techniques used to find such a pattern, however a group of students in MIT including R. William Gosper, Robert April, Michael Beeler, Richard Howell, Rich Schroeppel and Michael Specier solved the problem finding a generator of periodic structures known in cellular automata literature as a glider gun. In this sense a question is if von Neumann noticed this device in his model, something that surely must exist.
With this we conclude that an universal constructor must have conditions to reproduce anyone of its components in at least one way. An universal constructor must be able to maintain a constant and unlimited growth, and most contradictory of all these features is that an universal constructor is not able to construct everything. This last characteristic has been demonstrated in the model of Conway on finding a configuration that cannot be constructed by any way and it can just exist as an initial configuration. This configuration was found by Roger Banks using a mathematical technique to prove that there is a ``Garden of Eden'' configuration in a rectangular area of
cells [2].