The General and Logical Theory of Automata

TL;DR: In 1951 von Neumann argued that self-reproduction is not paradoxical if a machine carries a description of itself that is used in two ways — interpreted as building instructions, and copied verbatim into the offspring — and that above some complexity threshold, machines can build machines as complex as themselves or more so. He anticipated the DNA/ribosome split two years before Watson and Crick, but neither his kinematic robot nor his cellular automaton could be built or even simulated on 1951 hardware. Today the cellular version runs on a laptop, biology has vindicated the architecture, and a physical self-replicating factory — the one thing nobody has seriously built — is finally an engineering problem rather than a philosophical one.

The idea, as von Neumann had it

The paper is a talk given at the 1948 Hixon Symposium on cerebral mechanisms and published in the 1951 proceedings (bibliographic details not independently verified here, but that is the standard citation). The intellectual backdrop is thin by modern standards: McCulloch–Pitts neurons (1943) had just shown that networks of threshold units are equivalent to logic, Turing's universal machine (1936) existed as pure mathematics, and the stored-program computer was a design document plus a handful of machines under construction. Against that backdrop, von Neumann asked two questions that he insisted were the real subject of computing: how do you get reliable behavior from unreliable components, and how can complexity increase rather than degrade when machines make machines?

The second question hides an apparent paradox. Intuitively, a constructor must be "more complicated" than its product — a machine shop is more elaborate than the widgets it stamps out. If that were a law, complexity could only decay down a chain of construction, and life (which evidently ratchets complexity up) would be impossible. Von Neumann's dissolution of the paradox is the lasting contribution, and it is essentially a fixed-point trick, cousin to Gödel numbering and Kleene's recursion theorem.

Take three components:

• A, a universal constructor: given a description \phi(X) of any machine X, it builds X from ambient parts.
• B, a copier: given any description, it duplicates it — blindly, without interpreting it.
• C, a controller that sequences the two and attaches the copied description to the finished offspring.

Now feed the aggregate D = A + B + C its own description \phi(D). The constructor interprets \phi(D) to build a new D'; the copier copies \phi(D) uninterpreted and inserts it into D'. The result is E = D + \phi(D), and E reproduces E. The infinite regress ("the description must contain a description of the description...") never starts, because the description is treated as passive data in one pathway and as executable specification in the other.

Two corollaries in the paper deserve emphasis. First, the complexity threshold: below some level of complication, automata can only produce simpler automata; above it, complication can be preserved or increased — von Neumann explicitly framed this as the precondition for evolution, noting that a mutation on the tape is heritable. Second, the constructor is universal: give it \phi(D + X) and it builds a self-reproducer that also makes X. That is a factory that copies itself while producing goods — the "seed factory" idea in one line.

In the Hixon talk the machine is kinematic: a robot floating in a sea of parts (girders, muscles, sensing organs), grabbing and welding. Von Neumann knew this fudged the physics, and following a suggestion from Ulam he later reworked it as a cellular automaton — a 2D grid of 29-state cells — worked out in lectures around 1952–53 and published posthumously as Theory of Self-Reproducing Automata (Burks, ed., 1966).

Why it could not work in 1951

Compute. The machine von Neumann was building at the IAS, roughly contemporaneous with the talk, had 1,024 words of 40-bit memory — about 5 KB — and executed on the order of 10^3–10^4 operations per second. His CA self-reproducer, when finally implemented, required a configuration of very roughly 10^5 non-quiescent cells (a large body plus a tape on the order of 10^5 cells) evolving in a larger arena for a great many steps. Even representing one snapshot exceeds 1951 memory by orders of magnitude; simulating the dynamics was out of the question by a factor of perhaps 10^9 or more. Nobody simulated the full design until Pesavento's implementation in the mid-1990s.

Hardware reliability. Vacuum tubes failed after hundreds to thousands of hours; a machine with thousands of tubes faulted every few hours. A physical constructor needing millions of reliable elementary operations per replication cycle was absurd — which is precisely why the other half of von Neumann's automata program was "Probabilistic Logics and the Synthesis of Reliable Organisms from Unreliable Components" (lectures 1952). Complexity and reliability were, for him, the same problem.

Everything physical. No servo-controlled manipulators (industrial robot arms arrive ~1961 with Unimate), no machine vision, no CAD, no additive manufacturing, no molecular biology to steal tricks from. The kinematic model wasn't just unbuildable; there was no discipline within which to attempt it. And the biological confirmation didn't exist yet: DNA's structure came in 1953, the genetic code in the early 1960s. Von Neumann's translate-vs-replicate split was a prediction, made from logic alone.

What changed

The cellular version is now trivial. Codd reduced the construction to 8 states (1968); Langton's loops (1984) showed minimal (non-universal) self-reproduction in under a hundred cells; Pesavento ran von Neumann's actual design. Any laptop simulates all of this in real time. The logical theory is fully vindicated in silico.

Biology confirmed the architecture. Genome as tape, ribosome as approximately-universal constructor, polymerases as copier, the code as the \phi mapping. The correspondence is so clean that Sydney Brenner argued von Neumann's scheme should be counted among the conceptual foundations of molecular biology.

The physical substrate now exists in pieces. Multi-material 3D printing, pick-and-place assembly, industrial arms with sub-millimeter repeatability, learned visuomotor policies that handle part variation, and DNA nanotechnology at the molecular end. The RepRap project (Bowyer, from ~2005) built a printer that prints a substantial fraction of its own parts — by part count, roughly half; by mass and by capability (motors, electronics, rods, extruder), much less. NASA's 1980 "Advanced Automation for Space Missions" study designed a self-replicating lunar factory on paper (a ~100-ton seed) and concluded the gap was autonomy and closure engineering, not physics. Forty-five years later, the autonomy gap is the one that has actually moved: foundation-model-driven manipulation is the missing controller von Neumann's kinematic robot never had.

A serious 2026 revival

The right project is a quantified-closure replication cell: a work envelope containing robot arms, printers, and basic subtractive/joining tools, plus AI control, that assembles a functioning copy of itself from feedstock. The scientific product is not the demo but the measurement. Define closure fractions

— the fraction of the offspring's mass, part count, and cost produced inside the cell rather than imported as "vitamins" (chips, motors, bearings). RepRap's honest lesson is that the last 20% of closure is nearly all the difficulty: semiconductors and precision components resist local fabrication. So the experiment should publish a closure curve — offspring quality and c over generations — rather than a binary "it replicated."

What to reuse from the paper: the strict separation of description and constructor (a versioned, machine-readable build spec that is both executed and copied — mutate it and you get heritable variation, i.e., an evolvable factory); the universality framing (the same cell must make products, not just copies, or it's a stunt); and the reliability question (error-correct the process, since physical assembly is noisy in ways CA cells are not — inspection-and-rework is the physical analogue of von Neumann's redundant logics).

What to replace: the sea of pre-made parts becomes explicit feedstock accounting; the tape becomes CAD plus assembly programs plus learned policies (note that policy weights are part of \phi(D) — the description now includes a neural network, which von Neumann of all people would have enjoyed); the controller C becomes a VLM-driven planner with force-feedback manipulation. The economics is the motivation: a cell with replication time T and closure c \to 1 gives exponentially growing manufacturing capacity from a fixed seed — the standard argument for lunar/asteroid industry, and the reason this is worth doing even at c \approx 0.9.

Tried, vindicated, open

Vindicated: the logic (CA implementations), the biology (molecular replication machinery), the quine/recursion-theorem formalization in computability theory. Partially tried: RepRap (physical, low closure), Zykov et al.'s modular self-reproducing cubes (Cornell, 2005 — physical but from prefabricated smart modules, so closure near zero), the NASA 1980 paper study, and recent "self-replicating factory" roadmapping in the space-resources community. Conceptual descendants: Deutsch and Marletto's constructor theory, artificial-life work on open-ended evolution, and arguably the entire fault-tolerance tradition from von Neumann's reliability lectures through modern ECC and redundant inference.

Still open, and genuinely so: no one has quantified von Neumann's complexity threshold — there is no accepted complexity measure under which "below this, degeneration; above this, growth" is a theorem about physical constructors. No physical system has demonstrated high material closure (c_{\text{mass}} > 0.9, say) with autonomous assembly. And the evolvability corollary — heritable variation in a physical manufacturing lineage — has never been demonstrated at all.

Where to read it

The Hixon talk, "The General and Logical Theory of Automata," appears in Cerebral Mechanisms in Behavior: The Hixon Symposium (Wiley, 1951) and is reprinted in von Neumann's Collected Works, vol. V (I have not verified page numbers; no stable link was available for this essay). Read it alongside: Burks (ed.), Theory of Self-Reproducing Automata (1966) for the full CA construction; von Neumann's "Probabilistic Logics" lectures for the reliability half; Freitas & Merkle, Kinematic Self-Replicating Machines (2004), the encyclopedic survey of everything attempted since; and Bowyer's RepRap papers for the only sustained physical experiment. For the biology connection, Brenner's essays on von Neumann and the genetic code are short and worth the hour.