Von Neumann universal constructor
Encyclopedia
John von Neumann
's Universal Constructor is a self-replicating 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 Self-Reproducing Automata, completed in 1966 by Arthur W. Burks
after von Neumann's death.
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.
, template replication and Langton's loops
. But von Neumann was interested in something more profound: construction universality and evolution.
This universal constructor can be seen as an abstract simulation
of a physical universal assembler.
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 structure of the DNA molecule by Watson and Crick
, though it followed the Avery-MacLeod-McCarty experiment
which identified DNA
as the molecular carrier of genetic information in living organisms. 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 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
.
Renato Nobili
and Umberto Pesavento published the first fully implemented self-reproducing cellular automaton in 1995, nearly fifty years after von Neumann's work. They used a 32-state cellular automaton 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 general 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.
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. Buckley 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; the same is true of Buckley's configurations.
In 2004, D. Mange et al. reported an implementation of a self-replicator that is consistent with the designs of von Neumann.
In 2009, Buckley published with Golly a third configuration for von Neumann 29-state cellular automata, which can perform either holistic self-replication, or self-replication by partial construction. This configuration also demonstrates that signal crossing is not necessary to the construction of self-replicators within von Neumann 29-state cellular automata.http://www.sourceforge.net/projects/golly
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.
It should be noted that none of the configurations discussed in this article is a universal constructor; none could, for instance, construct the real-time crossing organ devised by Gorman. To date, no configuration capable of universal construction has been demonstrated for the 29-state model of von Neumann.
algorithm was extended to support the 29-state and 32-state rulesets in Golly. On a modern desktop PC, replication now takes only a few minutes, although a significant amount of memory is required.
John von Neumann
John von Neumann was a Hungarian-American mathematician and polymath who made major contributions to a vast number of fields, including set theory, functional analysis, quantum mechanics, ergodic theory, geometry, fluid dynamics, economics and game theory, computer science, numerical analysis,...
's Universal Constructor is a self-replicating machine
Self-replicating machine
A self-replicating machine is an artificial construct that is theoretically capable of autonomously manufacturing a copy of itself using raw materials taken from its environment, thus exhibiting self-replication in a way analogous to that found in nature. The concept of self-replicating machines...
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 Self-Reproducing Automata, completed in 1966 by Arthur W. Burks
Arthur Burks
Arthur Walter Burks was an American mathematician who in the 1940s as a senior engineer on the project contributed to the design of the ENIAC, the first general-purpose electronic digital computer. Decades later, Burks and his wife Alice Burks outlined their case for the subject matter of the...
after von Neumann's death.
Von Neumann's specification
Von Neumann cellular automata
Von Neumann cellular automata are the original expression of cellular automata, the development of which were prompted by suggestions made to John von Neumann by his close friend and fellow mathematician Stanisław Ulam...
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. However it is clear that far simpler machines can achieve self-replication. Examples include trivial crystal-like growthCrystal growth
A crystal is a solid material whose constituent atoms, molecules, or ions are arranged in an orderly repeating pattern extending in all three spatial dimensions. Crystal growth is a major stage of a crystallization process, and consists in the addition of new atoms, ions, or polymer strings into...
, template replication and Langton's loops
Langton's loops
Langton's loops are a particular "species" of artificial life in a cellular automaton created in 1984 by Christopher Langton. They consist of a loop of cells containing genetic information, which flows continuously around the loop and out along an "arm" , which will become the daughter loop...
. But von Neumann was interested in something more profound: construction universality and evolution.
This universal constructor can be seen as an abstract simulation
Simulation
Simulation is the imitation of some real thing available, state of affairs, or process. The act of simulating something generally entails representing certain key characteristics or behaviours of a selected physical or abstract system....
of a physical universal assembler.
Note that the simpler self-replicating CA structures (especially, Byl's loop
Byl's loop
The Byl's loop is an artificial lifeform similar in concept to Langton's loop. It is a two-dimensional, 5-neighbor cellular automaton with 6 states per cell, and was developed in 1989 by John Byl, from the Department of Mathematical Sciences of Trinity Western University.- Details :The Byl's loop...
and the Chou-Reggia loop) cannot exist in a wide variety of forms and thus have very limited evolvability
Evolvability
Evolvability is defined as the capacity of a system for adaptive evolution. Evolvability is the ability of a population of organisms to not merely generate genetic diversity, but to generate adaptive genetic diversity, and thereby evolve through natural selection.In order for a biological organism...
. 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
Garden of Eden pattern
In a cellular automaton, a Garden of Eden configuration is a configuration that cannot appear on the lattice after one time step, no matter what the initial configuration. In other words, these are the configurations with no predecessors....
. 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 structure of the DNA molecule by Watson and Crick
Watson and Crick
James D. Watson and Francis Crick were the two co-discoverers of the structure of DNA in 1953. They used x-ray diffraction data collected by Rosalind Franklin and proposed the double helix or spiral staircase structure of the DNA molecule...
, though it followed the Avery-MacLeod-McCarty experiment
Avery-MacLeod-McCarty experiment
The Avery–MacLeod–McCarty experiment was an experimental demonstration, reported in 1944 by Oswald Avery, Colin MacLeod, and Maclyn McCarty, that DNA is the substance that causes bacterial transformation...
which identified DNA
DNA
Deoxyribonucleic acid is a nucleic acid that contains the genetic instructions used in the development and functioning of all known living organisms . The DNA segments that carry this genetic information are called genes, but other DNA sequences have structural purposes, or are involved in...
as the molecular carrier of genetic information in living organisms. 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 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
Natural selection
Natural selection is the nonrandom process by which biologic traits become either more or less common in a population as a function of differential reproduction of their bearers. It is a key mechanism of evolution....
.
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
Renato Nobili
Renato Nobili is the Galileo Galilei professor of physics at the University of Padova, Padova, Italy.Nobili's significant works include:* demonstration of self-replication in a 32-state cellular automaton;* work relating to the human cochlea....
and Umberto Pesavento published the first fully implemented self-reproducing cellular automaton in 1995, nearly fifty years after von Neumann's work. They used a 32-state cellular automaton instead of von Neumann's original 29-state specification
Von Neumann cellular automata
Von Neumann cellular automata are the original expression of cellular automata, the development of which were prompted by suggestions made to John von Neumann by his close friend and fellow mathematician Stanisław Ulam...
, extending it to allow for easier signal-crossing and a more compact design. They also published an implementation of a general 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.
In 2007, Nobili published a 32-state implementation that uses run-length encoding
Run-length encoding
Run-length encoding is a very simple form of data compression in which runs of data are stored as a single data value and count, rather than as the original run...
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. Buckley 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; the same is true of Buckley's configurations.
In 2004, D. Mange et al. reported an implementation of a self-replicator that is consistent with the designs of von Neumann.
In 2009, Buckley published with Golly a third configuration for von Neumann 29-state cellular automata, which can perform either holistic self-replication, or self-replication by partial construction. This configuration also demonstrates that signal crossing is not necessary to the construction of self-replicators within von Neumann 29-state cellular automata.http://www.sourceforge.net/projects/golly
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.
Comparison of implementations
| implementation | source | ruleset | rectangular area | number of cells | length of tape | ratio | timesteps for replication | tape code compression | tape code length | replication mechanism | replication type | growth rate |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Nobili-Pesavento, 1995 | http://www.sq3.org.uk/Evolution/JvN/ | Nobili 32-state | 97 × 170 | 6,329 | 145,315 | 22.96 | 6.34 × 1010 | none | 5 bits | holistic constructor | non-repeatable | linear |
| Nobili, 2007 | SR_CCN_AP.EVN http://www.pd.infn.it/~rnobili/wjvn/index.htmhttp://sourceforge.net/mailarchive/forum.php?thread_name=aac498730807310217udbc6fd8y809c16003ceb3782%40mail.gmail.com&forum_name=golly-test | Nobili 32-state | 97 × 100 | 5,313 | 56,325 | 10.60 | 9.59 × 109 | run-length limited encoding | 5 bits | holistic constructor | repeatable | super-linear |
| Buckley, 2009 | codon3.rle | Nobili 32-state | 116 × 95 | 4,855 | 23,577 | 4.86 | 1.63 x 109 | auto-retraction/bit generation/code overlay | 3 bits | holistic constructor | repeatable | super-linear |
| Buckley, 2008 | codon4.rle http://www.sourceforge.net/projects/golly | Nobili 32-state | 109 × 59 | 3,574 | 37,780 | 10.57 | 4.31 x 109 | auto-retraction/bit generation | 4 bits | holistic constructor | repeatable | linear |
| Buckley, 2008 | codon5.rle http://www.sourceforge.net/projects/golly | Nobili 32-state | 112 × 50 | 3,343 | 44,155 | 13.21 | 5.87 x 109 | auto-retraction | 5 bits | holistic constructor | repeatable | linear |
| Buckley, 2008 | replicator.mc http://tomas.rokicki.com/golly-1.5a-win.zip | von Neumann 29-state | 312 × 132 | 18,589 | 294,844 | 15.86 | 2.61 × 1011 | auto-retraction | 5 bits | holistic constructor | repeatable | linear |
| Buckley, 2009 | PartialReplicator.mc http://www.sourceforge.net/projects/golly | von Neumann 29-state | NA | NA | NA | - | ~1.12 x 1014 | none | 4 bits | partial constructor | repeatable | linear |
It should be noted that none of the configurations discussed in this article is a universal constructor; none could, for instance, construct the real-time crossing organ devised by Gorman. To date, no configuration capable of universal construction has been demonstrated for the 29-state model of von Neumann.
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 hashlifeHashlife
Hashlife is a memoized algorithm for computing the long-term fate of a given starting configuration in Conway's Game of Life and related cellular automata, much more quickly than would be possible using alternative algorithms that simulate each time step of each cell of the automaton...
algorithm was extended to support the 29-state and 32-state 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 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
- Codd's cellular automatonCodd's cellular automatonCodd's cellular automaton is a cellular automaton devised by the British computer scientist Edgar F. Codd in 1968. It was designed to recreate the computation- and construction-universality of von Neumann's CA but with fewer states: 8 instead of 29...
- Langton's loopsLangton's loopsLangton's loops are a particular "species" of artificial life in a cellular automaton created in 1984 by Christopher Langton. They consist of a loop of cells containing genetic information, which flows continuously around the loop and out along an "arm" , which will become the daughter loop...
- Nobili cellular automataNobili cellular automataNobili cellular automata are a variation of von Neumann cellular automata, in which additional states provide means of memory and the interference-free crossing of signal. Nobili cellular automata are the invention of Renato Nobili, a professor of physics at the University of Padova in Padova, Italy...
- Quine (computing)
- Self-replicating machineSelf-replicating machineA self-replicating machine is an artificial construct that is theoretically capable of autonomously manufacturing a copy of itself using raw materials taken from its environment, thus exhibiting self-replication in a way analogous to that found in nature. The concept of self-replicating machines...
- Santa Claus machineSanta Claus machineA Santa Claus Machine, named after the folkloric Santa Claus, is a hypothetical machine that is capable of creating any required object or structure out of any given material. It is most often referenced by futurists and science fiction writers when discussing hypothetical projects of enormous...
- Von Neumann cellular automataVon Neumann cellular automataVon Neumann cellular automata are the original expression of cellular automata, the development of which were prompted by suggestions made to John von Neumann by his close friend and fellow mathematician Stanisław Ulam...
- Wireworld
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 Self-Reproducing Universal Constructor The original Nobili-Pesavento source code, animations and Golly files of the replicators.
- John von Neumann's 29 state Cellular Automata Implemented in OpenLaszlo by Don HopkinsDon HopkinsDon Hopkins is an artist and programmer specializing in human computer interaction and computer graphics.He inspired Richard Stallman, who described him as a "very imaginative fellow", to use the term copyleft. He coined Deep Crack as the name of the EFF DES cracker, and built "AJAXian"...
- A Catalogue of Self-Replicating Cellular Automata. This catalogue complements the Proc. Automata 2008 volume.