Von Neumann universal constructor
John von Neumann's Universal Constructor is a selfreplicating machine in a cellular automata (CA) environment. It was designed in the 1940s, without the use of a computer. The fundamental details of the machine were published in von Neumann's book Theory of SelfReproducing Automata, completed in 1966 by Arthur W. Burks after von Neumann's death.^{[2]}
Von Neumann's specification defined the machine as using 29 states, these states constituting means of signal carriage and logical operation, and acting upon signals represented as bit streams. A 'tape' of cells encodes the sequence of actions to be performed by the machine. Using a writing head (termed a construction arm) the machine can print out (construct) a new pattern of cells, allowing it to make a complete copy of itself, and the tape.
Contents
Purpose
Von Neumann's design has traditionally been understood to be a demonstration of the logical requirements for machine selfreplication.^{[3]} However it is clear that far simpler machines can achieve selfreplication. Examples include trivial crystallike growth, template replication and Langton's loops. But von Neumann was interested in something more profound: construction universality and evolution.^{[4]}
This universal constructor can be seen as an abstract simulation of a physical universal assembler.
Note that the simpler selfreplicating CA structures (especially, Byl's loop and the ChouReggia loop) cannot exist in a wide variety of forms and thus have very limited evolvability. Other CA structures such as the Evoloop are somewhat evolvable but still don't support openended evolution. Commonly, simple replicators do not fully contain the machinery of construction, there being a degree to which the replicator is information copied by its surrounding environment. Although the Von Neumann design is a logical construction, it is in principle a design that could be instantiated as a physical machine. The issue of the environmental contribution to replication is somewhat open, since there are different conceptions of raw material and its availability.
The concept of a universal constructor is nontrivial because of the existence of garden of eden patterns. But a simple definition is that a universal constructor is able to construct any finite pattern of nonexcited (quiescent) cells.
Von Neumann's crucial insight is that part of the replicator has a double use; being both an active component of the construction mechanism, and being the target of a passive copying process. This part is played by the tape of instructions in Von Neumann's combination of universal constructor plus instruction tape.
The combination of a universal constructor and a tape of instructions would i) allow selfreplication, and also ii) guarantee that the openended complexity growth observed in biological organisms was possible.^{[3]} The image below illustrates this possibility.
This insight is all the more remarkable because it preceded the discovery of the structure of the DNA molecule by Watson and Crick, though it followed the AveryMacLeodMcCarty experiment which identified DNA as the molecular carrier of genetic information in living organisms.^{[5]} The DNA molecule is processed by separate mechanisms that carry out its instructions and copy the DNA for insertion for the newly constructed cell. The ability to achieve openended evolution lies in the fact that, just as in nature, errors (mutations) in the copying of the genetic tape can lead to viable variants of the automaton, which can then evolve via natural selection.
Implementation
Arthur Burks and others extended the work of von Neumann, giving a much clearer and complete set of details regarding the design and operation of von Neumann's selfreplicator. The work of J. W. Thatcher is particularly noteworthy, for he greatly simplified the design. Still, their work did not yield a complete design, cell by cell, of a configuration capable of demonstrating selfreplication.
Renato Nobili and Umberto Pesavento published the first fully implemented selfreproducing cellular automaton in 1995, nearly fifty years after von Neumann's work.^{[1]}^{[6]} They used a 32state cellular automaton instead of von Neumann's original 29state specification, extending it to allow for easier signalcrossing, explicit memory function and a more compact design. They also published an implementation of a general constructor within the original 29state CA but not one capable of complete replication  the configuration cannot duplicate its tape, nor can it trigger its offspring; the configuration can only construct.^{[6]}^{[7]}
In 2004, D. Mange et al. reported an implementation of a selfreplicator that is consistent with the designs of von Neumann.^{[8]}
In 2007, Nobili published a 32state implementation that uses runlength encoding to greatly reduce the size of the tape.^{[9]}
In 2008, William R. Buckley published two configurations which are selfreplicators within the original 29state CA of von Neumann.^{[7]} Buckley claims that the crossing of signal within von Neumann 29state cellular automata is not necessary to the construction of selfreplicators.^{[7]} Buckley also points out that for the purposes of evolution, each replicator should return to its original configuration after replicating, in order to be capable (in theory) of making more than one copy. As published, the 1995 design of NobiliPesavento does not fulfill this requirement but the 2007 design of Nobili does; the same is true of Buckley's configurations.
In 2009, Buckley published with Golly a third configuration for von Neumann 29state cellular automata, which can perform either holistic selfreplication, or selfreplication by partial construction. This configuration also demonstrates that signal crossing is not necessary to the construction of selfreplicators within von Neumann 29state cellular automata.
C. L. Nehaniv in 2002, and also Y. Takada et al. in 2004, proposed a universal constructor directly implemented upon an asynchronous cellular automaton, rather than upon a synchronous cellular automaton. ^{[10]} ^{[11]}
Comparison of implementations
implementation  source  ruleset  rectangular area  number of cells  length of tape  ratio  timesteps for replication  tape code compression  tape code length  tape code type  replication mechanism  replication type  growth rate 

NobiliPesavento, 1995 ^{[1]}  ^{[12]}  Nobili 32state  97 × 170  6,329  145,315  22.96  6.34 × 10^{10}  none  5 bits  binary  holistic constructor  nonrepeatable  linear 
Nobili, 2007  SR_CCN_AP.EVN ^{[13]}  Nobili 32state  97 × 100  5,313  56,325  10.60  9.59 × 10^{9}  runlength limited encoding  5 bits  binary  holistic constructor  repeatable  superlinear 
Buckley, 2008  codon5.rle ^{[14]}  Nobili 32state  112 × 50  3,343  44,155  13.21  5.87 x 10^{9}  autoretraction  5 bits  binary  holistic constructor  repeatable  linear 
Buckley, 2008^{[7]}  replicator.mc ^{[15]}  von Neumann 29state  312 × 132  18,589  294,844  15.86  2.61 × 10^{11}  autoretraction  5 bits  binary  holistic constructor  repeatable  linear 
Buckley, 2008  codon4.rle ^{[14]}  Nobili 32state  109 × 59  3,574  37,780  10.57  4.31 x 10^{9}  autoretraction/bit generation  4 bits  binary  holistic constructor  repeatable  linear 
Buckley, 2009  codon3.rle  Nobili 32state  116 × 95  4,855  23,577  4.86  1.63 x 10^{9}  autoretraction/bit generation/code overlay  3 bits  binary  holistic constructor  repeatable  superlinear 
Buckley, 2009  PartialReplicator.mc ^{[14]}  von Neumann 29state  2063 × 377  264,321  NA    ~1.12 x 10^{14}  none  4 bits  binary  partial constructor  repeatable  linear 
Goucher & Buckley, 2012  phi9.rle ^{[16]}  Nobili 32state  122 × 60  3957  8920  2.25    autoretraction/bit generation/code overlay/run length limited  3+ bits  ternary  holistic constructor  repeatable  superlinear 
As defined by von Neumann, universal construction entails the construction of passive configurations, only. As such, the concept of universal construction constituted nothing more than a literary (or, in this case, mathematical) device. It facilitated other proof, such as that a machine well constructed may engage in selfreplication, while universal construction itself was simply assumed over a most minimal case. Universal construction under this standard is trivial. Hence, while all the configurations given here can construct any passive configuration, none can construct the realtime crossing organ devised by Gorman.^{[7]}
Practicality
Computational cost
All the implementations of von Neumann's selfreproducing machine require considerable resources to run on computer. For example, in the NobiliPesavento 32state implementation shown above, while the body of the machine is just 6,329 nonempty cells (within a rectangle of size 97x170), it requires a tape that is 145,315 cells long, and takes 63 billion timesteps to replicate. A simulator running at 1,000 timesteps per second would take over 2 years to make the first copy. In 1995, when the first implementation was published, the authors had not seen their own machine replicate. However, in 2008, the hashlife algorithm was extended to support the 29state and 32state rulesets in Golly. On a modern desktop PC, replication now takes only a few minutes, although a significant amount of memory is required.
Evolvability
Von Neumann's stated problem was evolution:^{[4]} how is the complexity growth and evolvability of biological organisms possible? His machine shows how it is logically possible, by using a universal constructor, but does not show how it is possible in practice. In his unfinished work he briefly considers conflict and interactions between replicators ^{[17]} but in practice his model is not likely to become a useful unit of evolution because it is too fragile.^{[3]}
Animation gallery

320 jump read arm.gif
Example of a 29state read arm.
See also
 Codd's cellular automaton
 Langton's loops
 Nobili cellular automata
 Quine (computing)
 Selfreplicating machine
 Santa Claus machine
 Von Neumann cellular automata
 Wireworld
References
 ↑ ^{1.0} ^{1.1} ^{1.2} Pesavento, Umberto (1995), "An implementation of von Neumann's selfreproducing machine" (PDF), Artificial Life, MIT Press, 2 (4): 337–354, PMID 8942052, doi:10.1162/artl.1995.2.337, archived from the original (PDF) on 20070418
 ↑ von Neumann, John (1966), Theory of SelfReproducing Automata., www.walenz.org, archived from the original (Scanned book online) on 20080105, retrieved 20080229 Unknown parameter
coauthors=
ignored (help)  ↑ ^{3.0} ^{3.1} ^{3.2} McMullin, B. (2000), "John von Neumann and the Evolutionary Growth of Complexity: Looking Backwards, Looking Forwards...", Artificial Life, 6 (4): 347–361, PMID 11348586, doi:10.1162/106454600300103674
 ↑ ^{4.0} ^{4.1} [1]^{[dead link]}
 ↑ Rocha, Luis M., "Von Neumann and Natural Selection.", Lecture Notes of I585Biologically Inspired Computing Course, Indiana University (PDF)
 ↑ ^{6.0} ^{6.1} Nobili, Renato; Pesavento, Umberto (1996), "Generalised von Neumann's Automata", in Besussi, E.; Cecchini, A., Proc. Artificial Worlds and Urban Studies, Conference 1 (PDF), Venice: DAEST
 ↑ ^{7.0} ^{7.1} ^{7.2} ^{7.3} ^{7.4} Buckley, William R. (2008), "Signal Crossing Solutions in von Neumann Selfreplicating Cellular Automata", in Andrew Adamatzky, Ramon AlonsoSanz, Anna Lawniczak, Genaro Juarez Martinez, Kenichi Morita, Thomas Worsch, Proc. Automata 2008 (PDF), Luniver Press, pp. 453–503
 ↑ Mange, Daniel; Stauffer, A.; Peparaolo, L.; Tempesti, G. (2004), "A Macroscopic View of Selfreplication", Proceedings of the IEEE, 92 (12): 1929–1945, doi:10.1109/JPROC.2004.837631
 ↑ [2]
 ↑ Nehaniv, Chrystopher L. (2002), "SelfReproduction in Asynchronous Cellular Automata", 2002 NASA/DoD Conference on Evolvable Hardware (1518 July 2002, Alexandria, Virginia, USA), IEEE Computer Society Press, pp. 201–209
 ↑ Takada, Yousuke; Isokawa, Teijiro; Peper, Ferdinand; Matsui, Nobuyuki (2004), "Universal Construction on SelfTimed Cellular Automata", in Sloot, P.M.A., ACRI 2004, LNCS 3305, pp. 21–30
 ↑ [3]
 ↑ [4][5]
 ↑ ^{14.0} ^{14.1} ^{14.2} [6]
 ↑ [7]
 ↑ [8]
 ↑ [9]^{[dead link]}
External links
 Golly  the Cellular Automata Simulation Accelerator Very fast implementation of state transition and support for JvN, GoL, Wolfram, and other systems.
 von Neumann's SelfReproducing Universal Constructor The original NobiliPesavento source code, animations and Golly files of the replicators.
 John von Neumann's 29 state Cellular Automata Implemented in OpenLaszlo by Don Hopkins
 A Catalogue of SelfReplicating Cellular Automata. This catalogue complements the Proc. Automata 2008 volume.