Von Neumanns Self-Reproducing Cellular Automaton

Von Neumann strongly believed that a general theory of computation in complex networks of automata such as cellular automata would be essential both for understanding complex systems in nature and for designing artificial complex systems. Von Neumann made foundational contributions to such a theory, and it is thus ironic that the standard model of computation, with a CPU, globally accessible memory, serial processing, and so on has been dubbed the von Neumann style architecture, and architectures such as cellular automata have been dubbed non-von Neumann style.  

Von Neumann s detailed solution to his question, What kind of logical organization is sufficient for an automaton to be able to reproduce itself was presented in his book Theory of Self-Reproducing Automata (von Neumann, 1966). The manuscript was incomplete at the time of von Neumann s death in 1957. The manuscript was edited and completed by Burks, who also gives an excellent detailed overview of von Neumann s system in Essay 1 of his book Essays on Cellular Automata (Burks, 1970a). 

This question has to be framed carefully so that it does not admit trivial solutions (e.g., one can easily design a CA in which Is reproduce themselves)—the automaton in question needs to have a minimal complexity. Von Neumann required that the automaton in question be equivalent in power to a universal Turing machine. 

The self-reproducing automaton that von Neumann constructed, here denoted as Me, is embedded in a two-dimensional cellular space with a particular CA rule and a particular initial configuration of states. The two-dimensional space is considered to be infinite, and all but a finite number of cells start out in a special quiescent state. 

The tape unit consists of a tape control and a tape. The tape is a linear array of cells that contains the information about M, the automaton to be constructed. In particular, it contains (in left-to-right order) (1) the x and y coordinates xo,yo) of the lower left-hand corner of the rectangle in which the new automata is to be constructed (the construction area ) (2) the width a and height /3 of that rectangle and (3) the cell states making up the automaton (listed in reverse order of where they are to be placed in the rectangle) and a asterisk indicating the end of the tape. 

---