Euler's Eyes
2026-10-27
Self-reproducing automata
In the last years of his life von Neumann asked himself a question that sounded like philosophy: can a machine build a copy of itself? The difficulty is logical. To build a copy, the machine needs a description of itself; but the description is part of the machine, so it would have to describe itself, and so on, in an endless regress.
Description, constructor and copier
Von Neumann’s way out, presented in lectures from 1948 on, was to separate three pieces:
- a constructor $A$, which reads a description $D(X)$ of any machine $X$ and builds $X$;
- a copier $B$, which copies any description without understanding it;
- a control $C$, which links the two.
Now give the machine $A + B + C$ its own description, $D(A + B + C)$. The constructor reads the description and builds a new machine $A + B + C$; the copier makes a copy of the description and hands it to the new machine. The result is a complete copy, with its own description. The regress ends because the description is used in two ways: once as instructions to carry out, and once as text to copy without reading.
A grid of cells
To make the idea rigorous, von Neumann needed a simple “universe” in which machines could be built. At Ulam’s suggestion, he used an infinite grid of little squares, each in one of 29 states, which all change at the same time, at each step, according to the states of the four neighbours. Inside this grid he designed a huge configuration, with an immense number of cells, able to read a tape, build a copy of itself and copy the tape. The work was left unfinished at his death and was completed and published by his collaborator Arthur Burks in 1966, under the title Theory of Self-Reproducing Automata.
These grids are now called cellular automata. In 1970 the Englishman John Conway invented one with only two states, alive and dead, and one-line rules: a live cell with 2 or 3 live neighbours (counting diagonals) survives; a dead cell with exactly 3 live neighbours is born; all others die or stay dead. The Game of Life, as Conway called it, is so rich that computers and self-copying machines can also be built in it.
Exercise: the blinker
In the Game of Life, three live cells in a horizontal row form the “blinker”. Show that at the next step they become a vertical row.
The middle cell has 2 live neighbours and survives. The end cells have only 1 live neighbour and die. The two cells just above and just below the middle have exactly 3 live neighbours (the three in the row) and are born. Result: a vertical row of three. By the same reasoning it becomes horizontal again at the following step, and the pattern blinks for ever.
Exercise: why the copier?
Why does von Neumann’s machine need a copier $B$? Wouldn’t it be enough for the constructor $A$ to build the description too?
To build the description from instructions, the description would have to contain a description of itself, which would contain another, and so on: the infinite regress from the start. The copier avoids this: it reproduces the description as a string of symbols, without needing another description to do so.
Sources: John von Neumann, “The general and logical theory of automata” (1948 lecture, published 1951) · John von Neumann and Arthur W. Burks (ed.), Theory of Self-Reproducing Automata (1966) · Martin Gardner, “The fantastic combinations of John Conway’s new solitaire game ‘life’”, Scientific American (1970).
All topics on John von Neumann · ← The biased coin that becomes fair · The legacy of John von Neumann →