Von Neumann’s Dream: Self-Replicating Machines

In 1948, John von Neumann posed a question that cut across mathematics, biology, and engineering with equal force: is it logically possible for a machine to build an exact copy of itself?

This was not an engineering question. Von Neumann was not trying to build such a machine. He was trying to prove that one could exist — that self-replication was not a special biological miracle, unique to living cells and beyond the reach of formal analysis, but a logical consequence of having the right kind of complexity. If he could show that a sufficiently capable machine could, in principle, replicate itself, then life’s most mysterious property — the ability to reproduce — became just another problem in mathematics.

The path from that question to a working answer took nearly a decade, required a key suggestion from his closest friend, and produced something so complicated it ran to approximately 200,000 cells on a theoretical grid. Von Neumann died before the work was published. But the proof he constructed, made public nine years after his death, set the intellectual stage for everything Conway would later simplify.

The Robot Arm He Had to Abandon

Von Neumann’s first attempt at the problem was physical in spirit. He imagined a robot floating in a lake filled with spare parts — motors, sensors, wires, structural members. The robot would reach out with its arms, select parts from the lake, and assemble a copy of itself. The copy, now surrounded by the same lake of parts, would do the same.

The image is vivid and intuitive. It also turned out to be a dead end.

The problem was not conceptual — the idea was obviously right in outline. The problem was mathematical. A continuous machine working in a continuous space, assembling parts of arbitrary shape and size, does not yield to clean formal analysis. You cannot write a finite set of rules that governs every possible configuration. Von Neumann could argue persuasively that the machine could work, but he could not prove it in a rigorous way. The kinematic model, as he and Ulam came to call it, was qualitatively sound and formally intractable.

Stanisław Ulam saved the project. He and von Neumann were close friends — von Neumann’s closest friend in the United States, by most accounts — and they had worked together at Los Alamos during the war years and remained in frequent contact afterward. Ulam had been thinking about a related problem: how to model crystal growth mathematically. His approach was to use a grid — a two-dimensional lattice of discrete cells, each in one of a finite number of states, each updating according to a rule that depended only on its immediate neighbors. The grid stripped away all the physical messiness. You got a universe of perfect mathematical precision: finite states, finite neighborhoods, exact rules.

Ulam suggested this framework to von Neumann around 1951 or 1952. Von Neumann immediately saw that it could work. If you gave each cell enough states — enough degrees of freedom — you could, in principle, represent wires, logic gates, memory, and construction mechanisms. The continuous robot became a pattern of cell states. The lake of parts became empty grid space. The arms of the robot became a construction signal propagating across the lattice.

This was the birth of cellular automata.

Twenty-Nine States

Von Neumann’s grid uses a von Neumann neighborhood: each cell is influenced by itself and its four orthogonal neighbors — north, south, east, west, but not diagonals. Each cell can occupy one of 29 distinct states. The rule table specifying how each state combination produces the next state is enormous — far too large to work through by hand — but it is finite and exact.

What do the 29 states actually represent? They fall into several functional categories:

The quiescent state (1 state). A cell in this state is “empty” — it does nothing and causes nothing. Most of the grid is in this state. It corresponds to blank space.

Transmission states (8 states). These are the wires. A transmission cell carries a signal in a particular direction — a binary pulse, either active or not — and passes it along to the next transmission cell in line. Four of these are “ordinary” transmission elements; four are “special” transmission elements that handle signal crossing and other routing tasks. Together they allow the construction to route binary information from one part of the grid to another.

Confluent states (4 states). These are the logic gates — cells that receive signals from multiple inputs and emit a signal based on some logical combination. They implement the AND, OR, and NOT operations that give the system its computational power.

Sensitized states (8 states). These are cells in the process of being constructed — states that represent the transition from quiescent to some functional state, triggered by construction signals arriving from the construction arm.

The construction arm states (8 states). These encode the active front of the construction process, the mechanism by which the machine extends itself into new territory.

The system is deeply layered. At its base is a kind of universal computer: the transmission and confluent states can implement any Boolean logic. On top of that sits a universal constructor: a mechanism that can, given the right instructions, build any pattern of cell states anywhere in the empty grid around it.

The Universal Constructor and the Tape

The key concept in von Neumann’s design — and the concept that makes self-replication logically inevitable rather than merely possible — is the universal constructor.

A universal constructor is a machine that can construct any object, given a description of that object. The description functions like a blueprint. The constructor reads the blueprint, uses its construction arm to place cell states in the specified pattern, and the object is built. Change the blueprint, and the constructor builds something different. Feed the constructor a blueprint of a simpler machine, and it builds that machine. Feed it a blueprint of a complex one, and it builds that.

This is the key move: if the constructor is universal, then the description can specify anything — including the constructor itself.

Von Neumann’s self-replicating configuration contains four logical components:

  1. A universal constructor — the mechanism that does the building.
  2. A universal copier — a separate mechanism that duplicates the tape without reading it.
  3. A description tape — a long string of encoded instructions specifying the complete machine (constructor plus copier plus tape).
  4. A supervisory unit — control logic that coordinates the sequence: first, read the tape and build a copy of the machine; then, copy the tape and attach it to the new machine; then, activate the new machine.

When this four-part system runs, it builds an exact duplicate of itself, complete with the tape. The duplicate then runs, building another duplicate. And so on.

The logical structure of this proof is deep. The description tape plays two roles: it is interpreted (read and acted upon by the constructor) and copied (duplicated by the copier without interpretation). This dual role — instruction and data, program and object — is the logical key to self-replication. You cannot replicate without it.

Von Neumann formalized this insight in 1948, four years before Watson and Crick described the structure of DNA. When the DNA story unfolded — a molecule that functions simultaneously as an instruction set (translated into proteins by ribosomes) and as data (copied by polymerases to produce new DNA) — biologists recognized the abstract structure immediately. Von Neumann had predicted, from pure logic, the architecture that life had discovered by evolution.

The Scale of It

The full self-replicating configuration, by rough estimate, requires approximately 200,000 cells in a non-quiescent state to instantiate. The construction tape alone — the encoded description of the entire machine — is prodigiously long. A later implementation in a closely related 32-state rule (Nobili and Pesavento’s 1995 version, which extended von Neumann’s states slightly to make signal crossing easier) required a tape 145,315 cells long and took 63 billion timesteps to complete a single replication.

This is not a practical machine. No one has ever run the full von Neumann constructor on a computer — the resource requirements, even for modern hardware, are prohibitive without clever engineering. But practicality was never the point. The point was existence: to prove that such a thing was possible in principle.

Von Neumann proved it. The proof is rigorous. The construction exists, at least on paper, and it works.

The Unfinished Book

Von Neumann was diagnosed with bone cancer in 1955. He died on February 8, 1957, at Walter Reed Army Medical Hospital in Washington, D.C. He was 53 years old.

The cellular automaton work was not finished. Von Neumann had developed the core logical framework and constructed the proof, but had not assembled the complete rule tables and final specifications into a publishable form. The manuscripts he left behind were dense, incomplete, and in several cases contradictory on technical details.

Arthur W. Burks, a logician and computer scientist who had worked with von Neumann at the Institute for Advanced Study, took on the task of completing the work. Burks was one of the few people alive who understood the material well enough to do it. He spent years reconstructing the arguments from von Neumann’s lecture notes, correspondence, and partial manuscripts — filling gaps, resolving contradictions, completing the rule tables, and writing the editorial apparatus needed to make the work accessible.

The result was Theory of Self-Reproducing Automata, published by the University of Illinois Press in 1966. It appeared nine years after von Neumann’s death, four years before Conway published his first rules for the Game of Life.

The timing matters. Conway was already working on cellular automata by the mid-1960s, and von Neumann’s work — by then well known in the mathematics and computer science communities, even before the book’s publication — was the explicit backdrop. The question Conway set out to answer was, in a sense, a response to von Neumann’s question: you’ve shown self-replication is possible with 29 states and an enormous construction. What is the minimum you actually need?

The Inversion Conway Performed

Von Neumann’s approach was completeness-first. He needed a system powerful enough to be a universal constructor — capable of building any pattern, not just itself — and he needed the logical proof to be airtight. The 29 states were the price of that rigor. Every state earned its place: the transmission elements, the confluent gates, the sensitized states, the construction arm. Nothing was wasted. But the result was staggering in complexity.

Conway’s goal was the opposite. He wanted the simplest possible rule — ideally two states, alive and dead — that could still, somewhere in its vast space of possible patterns, support self-replication and universal computation. He was not trying to engineer a specific self-replicating machine. He was trying to find a rule under which self-replication would emerge — arise spontaneously from the right initial conditions, without being explicitly programmed in.

Conway imposed several constraints on himself. The rule should not produce explosive growth — patterns should generally stabilize. Small patterns should behave unpredictably enough to be interesting. And somewhere in the rule’s behavior space, there should exist patterns capable of von Neumann-style universal construction.

The Life rules he eventually settled on satisfy all three constraints. Life is Turing complete. Within the Life universe, it is possible to build a universal constructor. And in 2010, a self-replicating configuration was finally demonstrated inside Conway’s Life — a pattern that builds copies of itself, using a mechanism that echoes, at a structural level, the one von Neumann designed in 1952. Read more about self-replication in Life →

Von Neumann proved that 29 states were sufficient. Conway found that 2 states were enough.

What Von Neumann Actually Established

It is easy to read the story of von Neumann’s cellular automaton as a precursor — a complicated prototype that Conway then improved. That reading misses what von Neumann was actually doing.

Von Neumann was not building a toy. He was establishing a logical theorem about the nature of complexity: that a machine of sufficient complexity necessarily contains, as a logical consequence of that complexity, the capacity to reproduce itself. Self-replication is not some additional property you bolt on. It is what happens when a system becomes capable enough — when it crosses the threshold of having a universal constructor.

This is the same logical structure as Turing’s result: once you have a system capable of universal computation, you have, as a consequence, the ability to simulate any computation, including the computation of simulating itself. Replication follows from power, as inevitably as self-reference follows from expressiveness.

Conway’s Life inherits this result. Because Life is Turing complete, it contains — somewhere in its vast behavior space — a universal constructor. And that universal constructor implies self-replication. The 2010 result was a proof of existence, but the existence was already guaranteed by von Neumann’s logic, applied to Conway’s simpler rule.

The history runs: von Neumann asked whether self-replication was possible, and proved it was. Conway asked what was the minimum rule under which it would emerge, and found it. Together, they established that self-replication is a logical property of sufficiently powerful systems — not a miracle, not a biological special case, but an inevitable consequence of reaching a certain level of computational capability.

The universe, it seems, learns to copy itself once it knows enough to try.

Further Reading