Universal Constructor
|
|
VonNeumann_universal_constructor.PNG
John von Neumann's Universal Constructor is a self-replicating machine in a cellular automaton environment. It was designed in the 1940's, without the use of a computer. The full details of the machine were published in a book finished after von Neumann's death:
- von Neumann, J. (1966) The theory of self reproducing automata. A. W. Burks (Ed.), Univ. of Illinous Press, Illinois.
The machine uses 29 states to simulate wires and signals. A 'tape' of cells encodes the sequence of actions to be performed by the machine. Using a writing head the machine can print out a new pattern of cells, allowing it to make a complete copy of itself plus the tape.
| Contents |
Purpose
von Neumann's machine has traditionally been understood to be a demonstration of the logical possibility of self-reproduction. The later discovery of far simpler machines that could achieve this (for example, Langton's loops) therefore tended to make von Neumann's machine look unnecessarily complicated.
However, a recent re-interpretation of von Neumann's work has restored its importance. The use of a universal construction mechanism allows the machine not only to copy itself but also variants of itself, were copying errors (mutations) to appear in the tape. Thus the machine can act as a unit of evolution and theoretically could evolve into more complex forms. Notably, von Neumann's use of a genetic tape for the storage of instructions predated the discovery of the structure of DNA.
The simplest self-replicating CA structures (especially, Byl's loop and the Chou-Reggia loop) do not have a separate genetic 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.
- McMullin, B. (2000) John von Neumann and the Evolutionary Growth of Complexity: Looking Backwards, Looking Forwards... Artificial Life 6(4):347-361.
Implementation
The universal constructor was first implemented in full by Renato Nobili and Umberto Pesavento, nearly fifty years after its creation. This work was written up as:
- Pesavento, U. (1995) An implementation of von Neumann's self-reproducing machine. Artificial Life 2(4):337-354.
Even though cellular automata can in general be executed extremely rapidly, the enormous size of the tape required to fully copy the machine means that a full cycle of self-replication has never been run, and is not likely to be in the near future. Thus the machine remains of theoretical and historical interest only, and is not practical for studying evolutionary processes.
See also
External links
The original Nobili and Pesavento source code is available at:
Images, updated source code, and pre-compiled binaries for Windows are available at: