Self-reproducing automata

We will investigate automata under two important and connected, aspects those of logics and of construction. We can organize our considerations under the headings of five main questions  

Von Neumann was able to construct a self-reproducing UTM embedded within a 29-state/5-cell neighborhood two-dimensional cellular automaton, composed of several tens of thousands of cells. It was, to say the least, an enormously complex machine . Its set of 29 states consist largely of various logical building blocks (AND and OR gates, for example), several types of transmission lines, data encoders and recorders, clocks, etc. Von Neumann was unfortunately unable to finish the proof that his machine was a UTM before his death, but the proof was later completed and published by Arthur Burks [vonN66]. 

Von Neumann s machine is actually an example of a universal constructor. It must not only carry out logical operations (i.e. act as a universal computer), but must also be able to identify and manipulate various components. The universal constructor C must be able to both (1) construct the machine whose blueprint appears in symbolic form on its input tape and (2) attach a copy of that same blueprint to the machine once it is constructed. Self-reproduction is the special case where C s input tape actually contains the blueprint data for C itself. Alas, there are a few subtleties. 

Suppose we start with an automaton A that is given a tape with a blueprint B a on it. The composite machine will then construct a copy of A but it is not, in and of itself, self-reproducing i.e, the aggregate machine A + creates A, not A + B. This situation is not remedied by simply adding a description of B to B, since in this case A + yields A + B and not A + B +Ba Thus, whatever we 

Von Neumann recognized this problem, of course. His solution was to essentially use the cooperative action of several automata to effectively copy a machine s blueprint. He first introduced a copier automaton M that copies whatever blueprint B it is given. Next, he defined an automaton A that inserts a copy of B into the 

---

Von Neumann, J. 1966. Theory of Self-Reproducing Automata. University of Illinois Press, Urbana, Illinois. 

J. Von Neumann, in Theory of Self-Reproducing Automata, A. W. Burks, Ed., University of... 

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). 

Burks, A. W. (1970c) Von Neumann s self-reproducing automata. In Burks (1970a). 

---