Von Neumann universal constructor

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.

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 W. Burks after von Neumann's death.[2] It is regarded as foundational for automata theory, complex systems, and artificial life.[3][4] 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."[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. He asked what is the threshold of complexity that must be crossed for machines to be able to evolve.[4] 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.[4][5]

To define his machine in more detail, von Neumann invented the concept of a cellular automaton. The 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'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[4]) 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.

  1. ^ Pesavento, Umberto (1995), "An implementation of von Neumann's self-reproducing machine" (PDF), Artificial Life, 2 (4), MIT Press: 337–354, doi:10.1162/artl.1995.2.337, PMID 8942052, archived from the original (PDF) on June 21, 2007
  2. ^ a b von Neumann, John; Burks, Arthur W. (1966), Theory of Self-Reproducing Automata. (Scanned book online), University of Illinois Press, retrieved 2017-02-28
  3. ^ McMullin, B. (2000), "John von Neumann and the Evolutionary Growth of Complexity: Looking Backwards, Looking Forwards...", Artificial Life, 6 (4): 347–361, doi:10.1162/106454600300103674, PMID 11348586, S2CID 5454783
  4. ^ a b c d Rocha, Luis M. (1998), "Selected Self-Organization and the Semiotics of Evolutionary Systems", Evolutionary Systems, Springer, Dordrecht, pp. 341–358, doi:10.1007/978-94-017-1510-2_25, ISBN 978-90-481-5103-5
  5. ^ a b Brenner, Sydney (2012), "Life's code script", Nature, 482 (7386): 461, doi:10.1038/482461a, PMID 22358811, S2CID 205070101