Universal Constructor

From Wikipedia, the free encyclopedia

The Nobili-Pesavento 29-state approximation of von Neumann's universal constructor, with a tape of instructions extending to the right.

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.

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.

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.

In 1968, Edgar F. Codd devised an 8-state 5-neighbor cellular automaton that he showed to be a universal computer-constructor. Five years later, in 1973, John Devore modified Codd's work and reduced the size of the self-reproducing machine.

1 Modeling open-ended evolution
2 Implementation
3 Feasibility
4 Demonstration
5 See also
6 References
7 External links

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

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.

[edit] Implementation

The first presentation of a plausible universal constructor design was given by Renato Nobili and Umberto Pesavento, nearly fifty years after its creation. 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. More recently, an implemention of a universal constructor that is consistent with the designs of von Neumann has come to light, however, work on the problem of signal crossing continues. Takada et al. also proposed a universal constructor directly implemented on an asynchronous cellular automaton, rather than by a simulation of a synchronous cellular automaton.

[edit] Feasibility

A plausible von Neumann universal constructor, with the input tape of instructions required for self-replication.

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.

[edit] Demonstration

The image to the right shows the Nobili-Pesavento 29-state machine with its 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.

[edit] See also

[edit] References

Burks, A. W. et. al. (1970) Essays on Cellular Automata. Univ. of Illinois Press.
John Devore and Ron Hightower. The Devore variation of the Codd self-replicating computer. Presented at Artificial Life III, Santa Fe, New Mexico, 1992.
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]
McMullin, B. (2000) John von Neumann and the Evolutionary Growth of Complexity: Looking Backwards, Looking Forwards... Artificial Life 6(4):347-361. [4]
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]
Pesavento, U. (1995) An implementation of von Neumann's self-reproducing machine. Artificial Life 2(4):337-354.[6]
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, 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.