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 a book finished after von Neumann's death. See:
- von Neumann, J. (1966) The theory of self reproducing automata. A. W. Burks (Ed.), Univ. of Illinois Press.
Von Neumann's specification defined the machine as using 29 states, these states consituting 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.
Arthur W. 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. See:
- Burks, A. W. et. al. (1970) Essays on Cellular Automata. Univ. of Illinois Press.
Purpose: Modeling Open-ended Evolution
Von Neumann's cellular automata has traditionally been understood to provide an environment suitable to demonstration of the logical requirements for machine self-replication. While the mathematical proof of self-replication was very important, von Neumann's self-reproducing cellular automaton has long been accepted in Theoretical Biology and Artificial Life to be more useful as a treatment of the logical requirements for open-ended evolution. Indeed, von Neumann understood that machines could easily achieve trivial forms of self-reproduction based on template-replication or crystal-like growth. In constrast, he observed that, unlike machines, biological organisms have the ability to increase their complexity without limit via self-replication (open-ended evolution).
His insight that open-ended evolution requires the separation of a universal constructor (a cellular automaton) from its own description (the tape), which needs to be copied separately is all the more remarkable because it preceded the discovery of the structure of the DNA molecule as a genetic information store in biological systems. The ability to achieve open-ended evolution lies in the fact that errors (mutations) in the copying of the description can lead to viable variants of the automaton, which can then evolve via Natural Selection. For a deeper treatment of open-ended evolution in von Neumann cellular automata, see:
- Pattee, H.H. (1982). "Cell psychology: An evolutionary approach to the symbol-matter problem". Cognition and Brain Theory 5(4), 325-341.
- Pattee, H.H. (1995) "Evolving self-reference: matter, symbols, and semantic closure". Communication and Cognition - Artificial Intelligence, 12 (1-2), 9-28. [1]
- Rocha, L.M. (1998)."Selected Self-Organization and the Semiotics of Evolutionary Systems". In: Evolutionary Systems: The Biological and Epistemological Perspectives on Selection and Self- Organization, . S. Salthe, G. Van de Vijver, and M. Delpos (eds.). Kluwer, pp. 341-358.[2]
- Rocha, L.M. (2001). "Evolution with material symbol systems". Biosystems. Vol. 60, pp. 95-121. [3]
It has been pointed out that far simpler machines achieve self-replication (for example, Langton's loops). However, such simpler machines are not capable of open-ended evolution. The simplest self-replicating CA structures (especially, Byl's loop and the Chou-Reggia loop) do not have a separate genetic description (tape) and cannot exist in a wide variety of forms, thus having very limited evolvability. In between are structures such as the Evoloop which are somewhat evolvable. See:
- McMullin, B. (2000) John von Neumann and the Evolutionary Growth of Complexity: Looking Backwards, Looking Forwards... Artificial Life 6(4):347-361. [4]
Implementation
The first presentation of a plausible universal constructor design was given by Renato Nobili and Umberto Pesavento, nearly fifty years after its creation. See:
- Nobili, R. and Pesavento, U. (1996) - Generalised von Neumann's Automata I: a Revisitation - in Artificial Worlds and Urban Studies, E.Besussi and A.Cecchini (Eds.), DAEST Pubblication, Convegni 1, Venezia. [5]
Nobili and Pesavento also presented an extension of von Neumann's CA, by adding three extra states that facilitate the crossing of signals. This allowed a much smaller version of the machine to be created, though at the cost of rendering the design to be not a true von Neumann self-replicating cellular automaton. See:
- Pesavento, U. (1995) An implementation of von Neumann's self-reproducing machine. Artificial Life 2(4):337-354.
More recently, an implemention of a universal constructor that is consistent with the designs of von Neumann has come to light. See:
- Mange, D. et. al. (2005) A Macroscopic View of Self-Replication. Proc. of the IEEE, Vol. 92, No. 12, December 2004, pp. 1929-1945.
Work on the problem of signal crossing continues. See:
- Buckley, W. R. and Mukherjee, A. (2005) Constructibility of Signal-Crossing Solutions in von Neumann 29-State Cellular Automata. V.S. Sunderam et al. (Eds.): ICCS 2005, LNCS 3515, pp. 395–403, 2005.
Takada et al. proposed a universal constructor directly implemented on an asynchronous cellular automaton, rather than by a simulation of a synchronous cellular automaton. See:
- Takada, Y. et al. (2004) Universal Construction on Self-Timed Cellular Automata. P.M.A. Sloot et al. (Eds.): ACRI 2004, LNCS 3305, pp. 21-30.
Practicality
Even though cellular automata can in general be executed extremely rapidly, the enormous size of the tape required to fully describe the self-replicating cellular automaton (the machine thereby instructed to direct production of a copy - or replicant) means that a full cycle of self-replication has never been demonstrated, fulfillment being a topic of current debate. However, accelerating improvements to computational throughput and capacity suggest this condition will in the near-term future reverse itself. Thus, while the machine is currently of theoretical and historical interest, it is expected to soon be of practical value in the study of evolutionary processes. Further, the flexibility of the von Neumann model suggests that it will also prove valuable for the study of fundamental biological processes, such as epigenesis and embryology. See:
- Buckley, W. R. and Mukherjee, A. (2005) Constructibility of Signal-Crossing Solutions in von Neumann 29-State Cellular Automata. V.S. Sunderam et al. (Eds.): ICCS 2005, LNCS 3515, pp. 395–403, 2005.
Demonstration
The image below shows the Nobili-Pesavento 29-state machine with its input tape. The tape contains a coded description of the machine, such as is required for self-replication. Tape content is represented in von Neumann's original 5-bit encoding scheme. This tape has over 84,000 cells. The world (system of cellular automata) shown wraps around and drops down 4 cells to enable the whole tape to be shown, although this prevents a complete copy of the tape being made as this would then overwrite the original. To unwrap the tape completely would thus require a cellular automata that was at least 85,000 cells wide.
References in popular culture
- In the futuristic computer game Deus Ex, the 'Universal Constructor' is a facility which appears to work by the principles of a nanofactory, allowing the user to convert raw materials into any conceivable product - from weapons to virii - given appropriate construction schematics. The 'UC' found in Deus Ex does not appear to be capable of self-replication without outside assistance.
See also
External links
The original Nobili-Pesavento source code is available at:
Images, updated source code, and pre-compiled binaries for Windows are available at:
Java applets implementing the 29-state transition rule:
Universal Constructors - the band loosely inspired by the concept