🔗 Von Neumann Universal Constructor

🔗 Mathematics

John von Neumann's universal constructor is a self-replicating machine in a cellular automata (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.

Von Neumann's goal was to specify an abstract machine which, when run, would replicate itself. In his design, the machine consists of three parts: a 'blueprint' for itself, a mechanism that can read any blueprint and construct the machine (sans blueprint) specified by that blueprint, and a 'copy machine' that can make copies of any blueprint. After the mechanism has been used to construct the machine specified by the blueprint, the copy machine is used to create a copy of that blueprint, and this copy is placed into the new machine, resulting in a working replication of the original machine. Some machines will do this backwards, copying the blueprint and then building a machine.

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 a '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' to build a copy of the machine, without tape, at some other location in the cell grid. The tape can't contain instructions to build an equally long tape, just as a container can't contain a container of the same size. Therefore, the machine contains a separate 'copy machine' which reads the tape and places a copy into the newly constructed machine. The resulting new machine and tape is identical to the old one, and it proceeds to replicate again.