Structures and Self-Replication — Machines That Copy Themselves

Before DNA was understood, a mathematician asked whether a machine could build a copy of itself — and answered it with a cellular automaton. Von Neumann's self-reproducing automaton proved that self-replication is possible in principle, and in doing so anticipated the logic of biological reproduction. This post is about the structures cellular automata can build, the deep question of self-reproduction, and what it taught us about life itself.

By Pratik Dhanave · May 25, 2026 · 7 min read

#Cellular Automata #Self-Replication #Von Neumann #Artificial Life #Complexity #Computer Science

Post 5 showed CAs can compute; this post shows they can reproduce — build working copies of themselves. Self-replication is one of the most profound capabilities cellular automata demonstrate, and its history (von Neumann, before the structure of DNA was known) is one of the great anticipations in science. It ties the series’ themes — emergence, computation — to the deepest question of all: what is life?

The question: can a machine reproduce itself?

In the 1940s, the mathematician John von Neumann posed a question that sounds almost paradoxical: can a machine build a copy of itself? The puzzle: it seems like a machine complex enough to build another machine must be more complex than what it builds (the builder needs blueprints plus construction machinery) — so a machine can’t build something as complex as itself, and self-reproduction seems impossible, or at least degenerative (each copy simpler than its parent). Yet living things reproduce, making copies as complex as themselves, generation after generation. How?

Von Neumann wanted a rigorous answer — not a hand-wave, but a proof that self-reproduction is logically possible, and an account of how. His insight was to abstract away the messy biology and chemistry and ask the question in a clean, formal setting: a cellular automaton. If he could construct, within a CA, a configuration of cells that builds a copy of itself by the CA’s rules, he’d have proven self-reproduction possible in principle and revealed its logical structure. This is a landmark use of CAs: not to model something, but to settle a deep conceptual question by construction.

Von Neumann’s answer and the logic of self-reproduction

Von Neumann succeeded (with a CA of 29 states per cell — more than Life’s two, needed for the construction). His self-reproducing automaton is a configuration of cells that, running under the CA rules, builds a complete copy of itself. The construction solved the “builder must be more complex” paradox with a beautiful piece of logic — the same logic, it turned out, that life uses:

A universal constructor. A machine that, given a description (a blueprint on a “tape”), builds whatever that description specifies — including another universal constructor. This is the construction machinery.
A description (blueprint). A stored description of the machine itself — the instructions for building it.
The crucial two-step trick. The constructor reads the description and builds the machine it describes (including a new constructor). Then — the key — it copies the description itself and attaches it to the new machine. So the offspring gets both the machine and the blueprint, making it a complete copy able to reproduce in turn.

The profound part is the dual use of the description: it’s interpreted (read as instructions, to build the machine) and it’s copied (treated as raw data, to pass on). This resolves the paradox — the blueprint doesn’t need to contain a blueprint-of-the-blueprint (infinite regress); it’s just copied verbatim as data. And here is the astonishing anticipation: this is exactly how DNA works. DNA is interpreted (translated into proteins — the machine) and copied (replicated and passed to offspring). Von Neumann worked out this logical structure of reproduction before the structure and role of DNA were understood — his CA predicted the fundamental logic that molecular biology later confirmed. A cellular automaton revealed a deep truth about life before biology did. That is one of the most remarkable results in the whole story of CAs.

Structures, self-replication, and what it means

Von Neumann’s construction sits atop the general fact (posts 3, 5) that CAs build structures — stable patterns, moving patterns, and patterns that construct and reproduce. The landscape of what CA structures can do:

Persistent and moving structures (posts 3): still lifes, oscillators, gliders, guns — the building blocks.
Constructing structures: von Neumann’s universal constructor builds arbitrary configurations from a description — construction, not just existence.
Self-replicating structures: configurations that build copies of themselves — von Neumann’s automaton, and later simpler ones (e.g., Langton’s loops, a much smaller self-replicating CA pattern that strips self-reproduction to its minimal loop-of-instructions essence, trading von Neumann’s universal-construction power for simplicity).

The significance of CA self-replication is deep: - It proves self-reproduction is possible in principle — not magic, not unique to biology, but a logical capability that any sufficiently rich rule-system can support. Life’s defining trick is formally understood and reproducible in an abstract medium. - It anticipated molecular biology (the interpret-and-copy logic of DNA), a stunning case of abstract math revealing biological truth in advance. - It founded artificial life — the study of life-like processes (reproduction, evolution, adaptation) in artificial media — and informs thinking about self-replicating machines (e.g., the idea of self-reproducing factories or spacecraft, “von Neumann probes”). If machines can reproduce in a CA, the principle extends to the physical world. - It deepens the emergence story: reproduction — the hallmark of life — emerges from simple local rules, with no vital essence required. Combined with computation (post 5), CAs show that the two signatures of life and mind, computing and reproducing, both arise from simple rules — a profound reframing of what life and complexity fundamentally are.

The through-line: John von Neumann used a cellular automaton to settle a deep question — can a machine build a copy of itself? — against the paradox that a builder seems to need to be more complex than what it builds. His self-reproducing automaton (a 29-state CA) answered yes, via a universal constructor that reads a description/blueprint and builds the machine it describes, plus the crucial two-step trick: the description is both interpreted (to build the machine) and copied (to pass on as data) — which resolves the paradox (no infinite regress of blueprints) and, astonishingly, is exactly how DNA works (translated into proteins and replicated) — worked out before DNA’s role was understood. CAs build a landscape of structures from persistent/moving patterns up to constructing and self-replicating ones (von Neumann’s; later the simpler Langton’s loops), proving self-reproduction is possible in principle in any rich-enough rule-system, anticipating molecular biology, founding artificial life and self-replicating-machine thinking, and showing that life’s hallmarks — computing and reproducing — both emerge from simple local rules with no vital essence required.

Key takeaways

John von Neumann asked whether a machine can build a copy of itself, against the paradox that a builder seems to need to be more complex than what it builds (so reproduction looks impossible/degenerative) — yet life reproduces copies as complex as itself; he sought a rigorous proof and chose a cellular automaton as the clean formal setting to settle it.
His self-reproducing automaton (a 29-state CA) answered yes, built from a universal constructor (builds whatever a description specifies, including another constructor) plus a stored description/blueprint, with the crucial two-step trick: the description is both interpreted (read as instructions to build the machine) and copied (treated as data and attached to the offspring) — so the copy gets both machine and blueprint.
The dual use of the description (interpreted and copied) resolves the paradox (no infinite regress) and is exactly how DNA works (translated into proteins and replicated) — von Neumann worked out this logical structure of reproduction before DNA’s role was understood, a stunning case of a CA revealing a biological truth in advance.
CAs build a landscape of structures: persistent/moving (still lifes, gliders, guns — posts 3), constructing (the universal constructor), and self-replicating (von Neumann’s; later the far simpler Langton’s loops, minimal self-reproduction trading construction power for simplicity).
CA self-replication is profound: it proves self-reproduction possible in principle (a logical capability of any rich-enough rule-system, not unique to biology), anticipated molecular biology, founded artificial life and self-replicating-machine thinking (e.g. von Neumann probes), and deepens the emergence story — life’s two hallmarks, computing (post 5) and reproducing, both arise from simple local rules with no vital essence required.