Von Neumann universal constructor

John von Neumann's universal constructor is a self-replicating machine in a cellular automaton (CA) environment.

"[5] Von Neumann's goal, as specified in his lectures at the University of Illinois in 1949,[2] was to design a machine whose complexity could grow automatically akin to biological organisms under natural selection.

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.

Von Neumann's design has traditionally been understood to be a demonstration of the logical requirements for machine self-replication.

[4] 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.

[4] As Brenner put it: Turing invented the stored-program computer, and von Neumann showed that the description is separate from the universal constructor.

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

[5]Von Neumann's goal, as specified in his lectures at the University of Illinois in 1949,[2] was to design a machine whose complexity could grow automatically akin to biological organisms under natural selection.

[5] 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.

[3] Thus, it is the conceptual model outlined in his Illinois lectures[2] that is of greater interest today because it shows how a machine can in principle evolve.

[6] 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.[4] 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.

[2]: 147 In automata theory, the concept of a universal constructor is non-trivial because of the existence of Garden of Eden patterns (configurations that have no predecessor).

Renato Nobili and Umberto Pesavento published the first fully implemented self-reproducing cellular automaton in 1995, nearly fifty years after von Neumann's work.

[1][8] They used a 32-state cellular automaton instead of von Neumann's original 29-state specification, extending it to allow for easier signal-crossing, explicit memory function and a more compact design.

This configuration also demonstrates that signal crossing is not necessary to the construction of self-replicators within von Neumann 29-state cellular automata.

The first implementation of von Neumann's self-reproducing universal constructor. [ 1 ] 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.
Von Neumann's System of Self-Replication Automata with the ability to evolve (Figure adapted from Luis Rocha 's Lecture Notes at Binghamton University [ 6 ] ). i) the self-replicating system is composed of several automata plus a separate description (an encoding formalized as a 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'). [ 4 ] The active process of construction from a description parallels DNA translation , the passive process of copying the description parallels DNA replication , and inheritance of mutated descriptions parallels Vertical inheritance of DNA mutations in Biology, [ 4 ] [ 5 ] 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. [ 6 ]
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.