View source for Von Neumann universal constructor

{{Short description|Self-replicating cellular automaton}}
[[Image:Nobili Pesavento 2reps.png|right|thumb|400px|The first implementation of von Neumann's self-reproducing universal constructor.<ref name=Pesavento1995>{{Citation|journal=Artificial Life| title=An implementation of von Neumann's self-reproducing machine| year=1995| first=Umberto| last=Pesavento|volume=2|issue=4|pages=337–354|publisher=MIT Press|url=http://dragonfly.tam.cornell.edu/~pesavent/pesavento_self_reproducing_machine.pdf|archive-url=https://web.archive.org/web/20070621164824/http://dragonfly.tam.cornell.edu/~pesavent/pesavento_self_reproducing_machine.pdf |archive-date=June 21, 2007 |doi=10.1162/artl.1995.2.337|pmid=8942052}}</ref> Three generations of machine are shown: the second has nearly finished constructing the third. The lines running to the right are the tapes of genetic instructions, which are copied along with the body of the machines. The machine shown runs in a 32-state version of von Neumann's cellular automata environment, not his original 29-state specification.]]

[[John von Neumann]]'s '''universal constructor''' is a [[self-replicating machine]] in a [[cellular automaton]] (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 Burks|Arthur W. Burks]] after von Neumann's death.<ref name=TSRA>{{Citation| url=https://archive.org/details/theoryofselfrepr00vonn_0| title=''Theory of Self-Reproducing Automata.''| author1=von Neumann, John| author2=Burks, Arthur W.| year=1966| publisher=University of Illinois Press| format=Scanned book online| access-date=2017-02-28}}</ref> It is regarded as foundational for [[automata theory]], [[complex systems]], and [[artificial life]].<ref name=McMullin2000>{{Citation|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/|doi=10.1162/106454600300103674|pmid=11348586|s2cid=5454783|url-access=subscription}}</ref><ref name=Rocha1998>{{Citation| year=1998| first=Luis M.| last=Rocha| title=Evolutionary Systems| chapter=Selected Self-Organization and the Semiotics of Evolutionary Systems|pages=341–358|publisher=Springer, Dordrecht| doi=10.1007/978-94-017-1510-2_25| isbn=978-90-481-5103-5|url=https://link.springer.com/chapter/10.1007/978-94-017-1510-2_25| url-access=subscription}}</ref> Indeed, Nobel Laureate [[Sydney Brenner]] considered von Neumann's work on self-reproducing automata (together with [[Turing]]'s work on computing machines) central to [[biological theory]] as well, allowing us to "discipline our thoughts about machines, both natural and artificial."<ref name=Brenner2012>{{Citation|journal=Nature| title=Life's code script| year=2012| first=Sydney| last=Brenner|volume=482| issue=7386|pages=461|url=https://www.nature.com/articles/482461a|doi=10.1038/482461a|pmid=22358811| s2cid=205070101|url-access=subscription}}</ref>

Von Neumann's goal, as specified in his lectures at the University of Illinois in 1949,<ref name="TSRA"/> was to design a machine whose complexity could grow automatically akin to biological organisms under [[Natural Selection|natural selection]]. He asked what is the ''threshold of complexity'' that must be crossed for machines to be able to evolve.<ref name=Rocha1998/> His answer was to specify an abstract machine which, when run, would replicate itself. In his design, the self-replicating machine consists of three parts: a "description" of ('blueprint' or program for) itself, a ''universal constructor'' mechanism that can read any description and construct the machine (sans description) encoded in that description, and a ''universal copy machine'' that can make copies of any description. After the universal constructor has been used to construct a new machine encoded in the description, the copy machine is used to create a copy of that description, and this copy is passed on to the new machine, resulting in a working replication of the original machine that can keep on reproducing. Some machines will do this backwards, copying the description and then building a machine. Crucially, the self-reproducing machine can evolve by accumulating mutations of the description, not the machine itself, thus gaining the ability to grow in complexity.<ref name=Rocha1998/><ref name=Brenner2012/>

To define his machine in more detail, von Neumann invented the concept of a [[cellular automata|cellular automaton]]. The [[Von Neumann cellular automaton|one he used]] consists of a two-dimensional grid of cells, each of which can be in one of 29 states at any point in time. At each timestep, each cell updates its state depending on the states of the surrounding cells at the prior timestep. The rules governing these updates are identical for all cells.

The universal constructor is a certain pattern of cell states in this cellular automaton. It contains one line of cells that serve as the description (akin to [[Turing machine|Turing's tape]]), encoding a sequence of instructions that serve as a 'blueprint' for the machine. The machine reads these instructions one by one and performs the corresponding actions. The instructions direct the machine to use its 'construction arm' (another automaton that functions like an [[operating system]]<ref name=Rocha1998/>) to build a copy of the machine, without the description tape, at some other location in the cell grid. The description cannot contain instructions to build an equally long description tape, just as a container cannot contain a container of the same size. Therefore, the machine includes the separate copy machine which reads the description tape and passes a copy to the newly constructed machine. The resulting new set of universal constructor and copy machines plus description tape is identical to the old one, and it proceeds to replicate again.

== Purpose ==

[[File:Von Neuman Self-replication 2.jpg|thumb|400px|right|Von Neumann's System of Self-Replication Automata with the ability to evolve (Figure adapted from [[Luis M. Rocha|Luis Rocha]]'s Lecture Notes at Binghamton University<ref name=Rocha_lec_notes>{{citation |last=Rocha|first=Luis M.| year=2015 |title=Lecture Notes of SSIE-583-Biologically Inspired Computing and Evolutionary Systems Course, Binghamton University|chapter=Chapter 6. Von Neumann and Natural Selection.|chapter-url=https://homes.luddy.indiana.edu/rocha/academics/i-bic/lec06.php|url=https://homes.luddy.indiana.edu/rocha/academics/i-bic/index.php#material}}</ref>). i) the self-replicating system is composed of several automata plus a separate description (an encoding formalized as a [[Turing Machine|Turing 'tape']]) of all the automata: Universal Constructor (A), Universal Copier (B), operating system (C), extra functions not involved with replication (D), and separate description Φ(A,B,C,D) encoding all automata. ii) (Top) Universal Constructor produces (decodes) automata from their description (''active'' mode of description); (Bottom) Universal Copier copies description of automata (''passive'' mode of description); Mutations Φ(D') to description Φ(D) (not changes in automaton D directly) propagate to the set of automata produced in next generation, allowing (automata + description) system to continue replicating and evolving (D → D').<ref name=Rocha1998/> The active process of construction from a description parallels [[Translation (biology)|DNA translation]], the passive process of copying the description parallels [[DNA replication]], and inheritance of mutated descriptions parallels [[Mutation|Vertical inheritance of DNA mutations]] in Biology,<ref name=Rocha1998/><ref name=Brenner2012/> and were proposed by Von Neumann before the discovery of the structure of the DNA molecule and how it is separately translated and replicated in the Cell.<ref name=Rocha_lec_notes/>]]

Von Neumann's design has traditionally been understood to be a demonstration of the logical requirements for machine self-replication.<ref name=McMullin2000/> However, it is clear that far simpler machines can achieve self-replication. Examples include trivial [[Crystal growth|crystal-like growth]], [[template replication]], and [[Langton's loops]]. But von Neumann was interested in something more profound: construction, universality, and evolution.<ref name=Rocha1998/><ref name=Brenner2012/>

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. Indeed, this universal constructor can be seen as an abstract [[simulation]] of a physical [[universal assembler]]. The issue of the environmental contribution to replication is somewhat open, since there are different conceptions of raw material and its availability.

Von Neumann's crucial insight is that the description of the machine, which is copied and passed to offspring separately via the universal copier, has a double use; being both an ''active'' component of the construction mechanism in reproduction, and being the target of a ''passive'' copying process. This part is played by the description (akin to [[Turing]]'s [[Turing machine|tape of instructions]]) in Von Neumann's combination of universal constructor and universal copier.<ref name=Rocha1998/> The combination of a universal constructor and copier, plus a tape of instructions conceptualizes and formalizes i) self-replication, and ii) open-ended evolution, or growth of complexity observed in biological organisms.<ref name=McMullin2000/>

This insight is all the more remarkable because it preceded the discovery of the structure of the DNA molecule by [[James Watson|Watson]] and [[Francis Crick|Crick]] and how it is separately translated and replicated in the cell—though it followed the [[Avery–MacLeod–McCarty experiment]] which identified [[DNA]] as the molecular carrier of genetic information in living organisms.<ref name=Rocha_lec_notes/> The DNA molecule is processed by separate mechanisms that carry out its instructions ([[Translation (biology)|translation]]) and copy ([[DNA replication|replicate]]) the DNA for newly constructed cells. The ability to achieve open-ended evolution lies in the fact that, just as in nature, errors ([[mutation]]s) in the copying of the genetic tape can lead to viable variants of the automaton, which can then evolve via [[Natural Selection|natural selection]].<ref name=Rocha1998/> As Brenner put it:

{{Quote
|text=Turing invented the stored-program computer, and von Neumann showed that the description is separate from the universal constructor. This is not trivial. Physicist Erwin Schrödinger confused the program and the constructor in his 1944 book What is Life?, in which he saw chromosomes as ″architect's plan and builder's craft in one″. This is wrong. The code script contains only a description of the executive function, not the function itself.<ref name=Brenner2012/>
|author=[[Sydney Brenner]]
}}

=== Evolution of Complexity ===

Von Neumann's goal, as specified in his lectures at the University of Illinois in 1949,<ref name="TSRA"/> was to design a machine whose complexity could grow automatically akin to biological organisms under [[Natural Selection|natural selection]]. He asked what is the ''threshold of complexity'' that must be crossed for machines to be able to evolve and grow in complexity.<ref name=Rocha1998/><ref name=McMullin2000/>  His “proof-of-principle” designs showed how it is logically possible. By using an architecture that separates a general purpose programmable (“universal”) constructor from a general purpose copier, he showed how the descriptions (tapes) of machines could accumulate mutations in self-replication and thus evolve more complex machines (the image below illustrates this possibility.). This is a very important result, as prior to that, it might have been conjectured that there is a fundamental logical barrier to the existence of such machines; in which case, biological organisms, which do evolve and grow in complexity, could not be “machines”, as conventionally understood. Von Neumann's insight was to think of life as a Turing Machine, which, is similarly defined by a state-determined machine "head" separated from a memory tape.<ref name=Brenner2012/>

In practice, when we consider the particular automata implementation Von Neumann pursued, we conclude that it does not yield much evolutionary dynamics because the machines are too fragile - the vast majority of perturbations cause them effectively to disintegrate.<ref name=McMullin2000/> Thus, it is the conceptual model outlined in his Illinois lectures<ref name="TSRA"/> that is of greater interest today because it shows how a machine can in principle evolve.<ref name=Pattee1995>{{Citation| first=Howard, H.| last=Pattee| title=LAWS, LANGUAGE and LIFE| chapter=Evolving Self-reference: Matter, Symbols, and Semantic Closure| series=Biosemiotics| date=2012|volume=12| issue=1–2|pages=9–27| doi=10.1007/978-94-007-5161-3_14| isbn=978-94-007-5160-6|chapter-url=https://link.springer.com/chapter/10.1007/978-94-007-5161-3_14}}</ref><ref name=Rocha1998/> This insight is all the more remarkable because the model preceded the discovery of the structure of the DNA molecule as discussed above.<ref name=Rocha_lec_notes/> It is also noteworthy that Von Neumann's design considers that mutations towards greater complexity need to occur in the (descriptions of) subsystems not involved in self-reproduction itself, as conceptualized by the additional automaton ''D'' he considered to perform all functions not directly involved in reproduction (see Figure above with Von Neumann's System of Self-Replication Automata with the ability to evolve.) Indeed, in biological organisms only very minor variations of the genetic code have been observed, which matches Von Neumann's rationale that the universal constructor (''A'') and Copier (''B'') would not themselves evolve, leaving all evolution (and growth of complexity) to automaton ''D''.<ref name=Rocha1998/> In his unfinished work, Von Neumann also briefly considers conflict and interactions between his self-reproducing machines, towards understanding the evolution of ecological and social interactions from his theory of self-reproducing machines.<ref name="TSRA"/>{{rp|147}}

[[Image:Pesavento replicator inherited mutations.png|thumb|center|700px|A demonstration of the ability of von Neumann's machine to support inheritable mutations. (1) At an earlier timestep, a mutation was manually added to the second generation machine's tape. (2) Later generations both display the [[phenotype]] of the mutation (a drawing of a flower) and pass the mutation on to their children, since the tape is copied each time. This example illustrates how von Neumann's design allows for complexity growth (in theory) since the tape could specify a machine that is more complex than the one making it.]]

== Implementations ==

In automata theory, the concept of a ''universal constructor'' is non-trivial because of the existence of [[Garden of Eden (cellular automaton)|Garden of Eden patterns]] (configurations that have no predecessor). But a simple definition is that a universal constructor is able to construct any finite pattern of non-excited (quiescent) cells.

[[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 cellular automaton in 1995, nearly fifty years after von Neumann's work.<ref name=Pesavento1995/><ref name=NobiliPesavento1996>{{Citation|last1=Nobili|first1=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}}</ref> They used a 32-state cellular automaton instead of von Neumann's original [[Von Neumann cellular automaton|29-state specification]], extending it to allow for easier signal-crossing, explicit memory function 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.<ref name=NobiliPesavento1996/><ref name=Automata2008/>

In 2004, D. Mange et al. reported an implementation of a self-replicator that is consistent with the designs of von Neumann.<ref>{{Citation|journal=Proceedings of the IEEE| title=A Macroscopic View of Self-replication| volume=92| issue=12| first1=Daniel| last1=Mange|last2=Stauffer|first2=A.|last3=Peparaolo|first3=L.|last4=Tempesti|first4=G.| pages=1929–1945| year=2004|doi=10.1109/JPROC.2004.837631| s2cid=22500865}}</ref>

In 2007, Nobili published a 32-state implementation that uses [[run-length encoding]] to greatly reduce the size of the tape.<ref name=nobili2007>{{cite web|url=http://www.pd.infn.it/~rnobili/wjvn/index.htm |title=The Cellular Automata of John von Neumann|first=Renato |last=Nobili|date=2007 |access-date=January 29, 2011 |url-status=dead |archive-url=https://web.archive.org/web/20110129003524/http://www.pd.infn.it/~rnobili/wjvn/index.htm |archive-date=January 29, 2011 }}</ref>

In 2008, William R. Buckley published two configurations which are self-replicators within the original 29-state CA of von Neumann.<ref name=Automata2008>{{Citation|title=Proc. Automata 2008|contribution=Signal Crossing Solutions in von Neumann Self-replicating Cellular Automata| year=2008| first=William R.| last=Buckley|editor=Andrew Adamatzky|editor-link=Andrew Adamatzky|editor2=Ramon Alonso-Sanz |editor3=Anna Lawniczak|editor3-link= Anna Lawniczak |editor4=Genaro Juarez Martinez |editor5=Kenichi Morita |editor6=Thomas Worsch |pages=453–503|publisher=Luniver Press|url=http://uncomp.uwe.ac.uk/free-books/automata2008reducedsize.pdf}}</ref> Buckley claims that the crossing of signal within von Neumann 29-state cellular automata is not necessary to the construction of self-replicators.<ref name=Automata2008/> 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 2009, Buckley published with [[Golly (program)|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.

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.
<ref>{{Citation|last=Nehaniv|first=Chrystopher L.|year=2002|contribution=Self-Reproduction in Asynchronous Cellular Automata|title=2002 NASA/DoD Conference on Evolvable Hardware (15-18 July 2002, Alexandria, Virginia, USA)|publisher=IEEE Computer Society Press|pages=201–209}}</ref>
<ref>{{Citation|last1=Takada|first1=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}}</ref>

=== Comparison of implementations ===
{{sort-under}}
{{table alignment}}
{| class="wikitable sortable sort-under col4center col5right col6right col7right col10right col12center"
|-
! Implementation !! Source !! Ruleset !! Rectangular area !! Number of cells !! Length of tape !! Ratio !! Period !! Tape code compression !! Tape code length !! Tape code type !! Replication mechanism !! Replication type !! Growth rate
|-
! Nobili-Pesavento, 1995<ref name=Pesavento1995/>
| {{CEmpty}}.<ref name=Pesavento1995/> || Nobili 32-state || 97&nbsp;×&nbsp;170 || 6,329 || 145,315 || 22.96 || {{val|6.34e10}} || {{CNone|none}} || 5 bits || binary || Holistic constructor || {{no2|non-repeatable}} || linear
|-
! Nobili, 2007
| SR_CCN_AP.EVN<ref name=nobili2007 /> || Nobili 32-state || 97&nbsp;×&nbsp;100 || 5,313 || 56,325 || 10.60 || {{val|9.59e9}} || run-length limited encoding || 5 bits || binary || Holistic constructor || {{yes2|repeatable}} || super-linear
|-
! Buckley, 2008
| codon5.rle<ref name="sourceforge.net">{{cite web|url=http://www.sourceforge.net/projects/golly|title=Golly, a Game of Life simulator|author=andykt|work=SourceForge|date=18 July 2023 }}</ref> || Nobili 32-state || 112&nbsp;×&nbsp;50 || 3,343 || 44,155 || 13.21 || {{val|5.87e9}} || auto-retraction || 5 bits || binary || Holistic constructor || {{yes2|repeatable}} || linear
|-
! Buckley, 2008<ref name=Automata2008/>
| replicator.mc || von Neumann 29-state || 312&nbsp;×&nbsp;132 || 18,589 || 294,844 || 15.86 || {{val|2.61e11}} || auto-retraction || 5 bits || binary || Holistic constructor || {{yes2|repeatable}} || linear
|-
! Buckley, 2008
| codon4.rle<ref name="sourceforge.net"/> || Nobili 32-state || 109&nbsp;×&nbsp;59 || 3,574 || 37,780 || 10.57 || {{val|4.31e9}} || {{hlist|auto-retraction|bit generation}} || 4 bits || binary || Holistic constructor || {{yes2|repeatable}} || linear
|-
! Buckley, 2009
| codon3.rle || Nobili 32-state || 116&nbsp;×&nbsp;95 || 4,855 || 23,577 || 4.86 || {{val|1.63e9}} || {{hlist|auto-retraction|bit generation|code overlay}}  || 3 bits || binary || Holistic constructor || {{yes2|repeatable}} || super-linear
|-
! Buckley, 2009
| PartialReplicator.mc<ref name="sourceforge.net"/> || von Neumann 29-state || 2063&nbsp;×&nbsp;377 || 264,321 || {{NA}} || {{NA}} || ≈{{val|1.12e14}} || {{CNone|none}}  || 4 bits || binary || {{partial}} constructor || {{yes2|repeatable}} || linear
|-
! Goucher & Buckley, 2012
| phi9.rle<ref>{{cite web|url=http://cp4space.wordpress.com/2012/11/12/self-replication/|title=Self-replication|work=Complex Projective 4-Space|date=12 November 2012 }}</ref> || Nobili 32-state || 122&nbsp;×&nbsp;60 || 3957 || 8920 || 2.25 || {{val|1.8e8}} || {{hlist|auto-retraction|bit generation|code overlay|run length limited}}  || 3+ bits || ternary || Holistic constructor || {{yes2|repeatable}} || super-linear
|}

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 self-replication, 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 real-time crossing organ devised by Gorman.<ref name="Automata2008"/>

== Practicality and 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 [[Golly (program)|Golly]]. On a modern desktop PC, replication now takes only a few minutes, although a significant amount of memory is required.

== Animation gallery ==
<gallery>
Image:320 jump read arm.gif|Example of a 29-state read arm.
</gallery>

== See also ==
*[[Codd's cellular automaton]]
*[[Langton's loops]]
*[[Nobili cellular automata]]
*[[Quine (computing)|Quine]], a program that produces itself as output
*[[Santa Claus machine]]
*[[Wireworld]]

== References ==
{{Reflist}}

== External links ==
*[http://www.donhopkins.com/drupal/node/41 John von Neumann's 29 state Cellular Automata Implemented in OpenLaszlo] by [[Don Hopkins]]

[[Category:Artificial life]]
[[Category:Cellular automaton patterns]]
[[Category:Self-replicating machines]]