Von Neumann universal constructor

John von Neumann's Universal Constructor is a self-replicating machine in a cellular automata 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 Self-Reproducing Automata", completed in 1966 by Arthur W. Burks after von Neumann's death.cite web| url=http://www.walenz.org/vonNeumann/index.html| title="Theory of Self-Reproducing Automata."| author=von Neumann, John| coauthors=Burks, Arthur W.| date=1966| publisher=www.walenz.org| format=Scanned book online| accessdate=2008-02-29]

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.

Purpose

Von Neumann's design has traditionally been understood to be a demonstration of the logical requirements for machine self-replication.cite journal|journal=Artificial Life|last=McMullin|first=B.|year=2000|title=John von Neumann and the Evolutionary Growth of Complexity: Looking Backwards, Looking Forwards...|volume=6|issue=4|pages=347-361|url=http://www.eeng.dcu.ie/~alife/bmcm-alj-2000/] However it is clear that far simpler machines can achieve self-replication. Examples include trivial crystal-like growth, template replication and Langton's loops. But von Neumann was interested in something more profound: construction universality and evolution. [http://www.walenz.org/vonNeumann/page0110.html]

Note that the simpler self-replicating CA structures (especially, Byl's loop and the Chou-Reggia 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 open-ended 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 non-trivial 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 non-excited (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 self-replication, and also ii) guarantee that the open-ended complexity growth observed in biological organisms was possible. The image below illustrates this possibility.

This insight is all the more remarkable because it preceded the discovery of the genetic information store in biological systems. The DNA molecule processed by separate mechanisms that carry out its instructions and copy the DNA for insertion for the newly constructed cell. The ability to achieve open-ended 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 self-replicator. 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 self-replication.

Renato Nobili and Umberto Pesavento published the first fully-implemented self-reproducing universal constructor in 1995, nearly fifty years after von Neumann's work.Citation|last=Nobili|first=Renato|last2=Pesavento|first2=Umberto|contribution=Generalised von Neumann's Automata|title=Proc. Artificial Worlds and Urban Studies, Conference 1|year=1996|editor-last=Besussi|editor-first=E.|editor2-last=Cecchini|editor2-first=A.|location=Venice|publisher=DAEST|url=http://www.pd.infn.it/%7Ernobili/pdf_files/jvnconstr.pdf|format=PDF] They used a 32-state cellular automaton (CA) instead of von Neumann's original 29-state specification, extending it to allow for easier signal-crossing and a more compact design. They also published an implementation of a universal constructor within the original 29-state 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, and its offspring are not self-replicable.

In 2007, Nobili published a 32-state implementation that uses run-length encoding to greatly reduce the size of the tape. [http://www.pd.infn.it/~rnobili/wjvn/index.htm]

In 2008, William R. Buckley published two configurations which are self-replicators within the original 29-state CA of von Neumann.Citation|title=Proc. Automata 2008|contribution=Signal Crossing Solutions in von Neumann Self-replicating Cellular Automata| year=2008| first=William R.| last=Buckley|editor-last=Andrew Adamatzky, Ramon Alonso-Sanz, Anna Lawniczak, Genaro Juarez Martinez, Kenichi Morita, Thomas Worsch|publisher=Luniver Press] Buckley also claims that the crossing of signal within von Neumann 29-state cellular automata is not necessary to the construction of self-replicators. 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 Nobili-Pesavento does not fulfill this requirement but the 2007 design of Nobili does.

Mange reports an implementation of a universal constructor that is consistent with the designs of von Neumann. [Citation|journal=Proceedings of the IEEE| title=A Macroscopic View of Self-replication| volume=92| issue=12| first=Daniel| last=Mange|last2=Stauffer|first2=A.|last3=Peparaolo|first3=L.|last4=Tempesti|first4=G.| pages=1929–1945| year=2004]

Takada et al. proposed a universal constructor directly implemented upon an asynchronous cellular automaton, rather than upon a synchronous cellular automaton. [Citation|last=Takada|first=Yousuke|last2=Isokawa|first2=Teijiro|last3=Peper|first3=Ferdinand
last4=Matsui|first4=Nobuyuki|year=2004|contribution=Universal Construction on Self-Timed Cellular Automata|editor-last=Sloot|editor-first=P.M.A.|title=ACRI 2004, LNCS 3305|pages=21-30]

Comparison of implementations

Practicality

Computational cost

All the implementations of von Neumann's self-reproducing machine require considerable resources to run on computer. For example, in the Nobili-Pesavento 32-state implementation shown above, while the body of the machine is just 6,329 non-empty 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 29-state and 32-state rulesets in [http://golly.sourceforge.net 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 [http://www.walenz.org/vonNeumann/page0110.html] : 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 [http://www.walenz.org/vonNeumann/page0147.html] but in practice his model is not likely to become a useful unit of evolution because it is too fragile.

See also

*Langton's loops
*Nobili cellular automata
*Quine (computing)
*Self-replicating machine
*Santa Claus machine
*Von Neumann cellular automata
*Wireworld

References

External links

* [http://golly.sourceforge.net Golly - the Cellular Automata Simulation Accelerator] Very fast implementation of state transition and support for JvN, GoL, Wolfram, and other systems.
* [http://www.sq3.org.uk/Evolution/JvN/ von Neumann's Self-Reproducing Universal Constructor] The original Nobili-Pesavento source code, animations and Golly files of the replicators.
* [http://www.donhopkins.com/drupal/node/41 John von Neumann's 29 state Cellular Automata Implemented in OpenLaszlo] by Don Hopkins