Computing Can Self-Replicate. That Doesn't Make

There is a seductive assumption threading through artificial life research: that if you build a system complex enough to compute anything, you are somewhere in the neighborhood of building something alive. Barbora Hudcova, a postdoctoral researcher at EPFL working with Clément Hongler, has spent considerable mathematical effort dismantling that assumption. Her recent talk at the Allen Discovery Center at Tufts University, titled "Computing is not Living," is a careful attempt to put formal boundaries around what self-replication actually requires — and to show that universal computation, on its own, doesn't cross them.

The argument unfolds through mathematics, but it begins with a genuinely old puzzle: how does a machine build a copy of itself without the builder being more complex than the built? The intuition that it cannot — that the constructor must contain a full description of the thing it constructs, plus the means to act on that description, and therefore must be strictly more complicated — haunted mechanistic thinking well into the nineteenth century. John von Neumann took that intuition seriously and then broke it.

The architecture of self-reproduction

Von Neumann's solution, worked out in the late 1940s, used cellular automata as the substrate. According to Wikipedia's documentation of the von Neumann universal constructor, his design operated on a 29-state, two-dimensional grid — a fact Hudcova also states explicitly in her talk. The pattern he constructed had three components: a supervisory unit that functions as a universal Turing machine, a construction arm capable of building arbitrary patterns in the cellular space, and a tape carrying instructions. The key insight was that the supervisory unit could operate in two distinct modes: one analogous to translation (interpreting instructions to build a new structure) and one analogous to transcription (copying the tape itself into the offspring). Both the information and the machinery for acting on it would be reproduced.

What makes this historically remarkable — and Hudcova dwells on this point — is timing. Von Neumann gave talks on these results in 1949, four years before Watson and Crick published the structure of DNA. The translation/transcription duality he described as a logical necessity for self-replication turned out to be precisely the architecture biology had independently arrived at. His contribution was only appreciated retrospectively.

The biological parallel is clean enough to be satisfying, but Hudcova is careful not to let it do too much work. The von Neumann construction is a proof that self-replication is logically possible in an abstract system; it doesn't tell us which properties of that system are actually load-bearing.

Quines and the question of sufficiency

Around the same time von Neumann was developing his automata, Stephen Kleene's recursion theorems were establishing something related in theoretical computer science. A corollary of those theorems is that in any Turing-complete programming language, there exists a program — called a quine — that outputs its own source code from an empty input. Every computationally universal system contains quines. Does that mean every computationally universal system supports self-replication?

Thomas Ray's Tierra, an artificial world from the early 1990s, made this question feel urgent. Ray hand-crafted an initial quine, seeded it into a shared memory environment where programs competed for execution time and space, and watched as the system evolved parasites, hyperparasites, and ecological dynamics that felt uncomfortably biological. A symbiogenesis-driven emergence of complex behaviors from simple replicating programs is, it turns out, a recurring motif in this literature.

But Hudcova argues Tierra-style systems are doing something subtler — and weaker — than von Neumann-style self-replication. In a quine-based system, the informational layer (the tape contents) replicates, but the functional layer (the Turing machine head and its state) gets duplicated by a rule baked into the underlying physics of the world. Ray had to hard-code the spawning of new virtual CPUs. The system's internal organization doesn't explain the copying of both layers; it explains only one, and outsources the other to the environment.

"The internal organization of our construction only explains self-replication of one half of the organism," Hudcova says, "and that is the informational layer. We had to somehow hard-code the copying of the functional layer into the underlying dynamics."

This is the intuitive core of the result she and her collaborators — Jordan Cotler, Clément Hongler, and Jonas Müller — set out to formalize.

Local versus global: a distinction that matters

Before arriving at the self-replication result, Hudcova spends considerable time sharpening the definition of computational universality itself, because it turns out "universal computation" is not one thing.

Local universality means a cellular automaton can simulate a universal Turing machine — encoding a finite computational state into a finite region of the automaton's infinite grid, running the dynamics, and decoding the result. The subtlety here is constraining what the encoder and decoder are permitted to do. If you leave them unconstrained, you can build a "universal" CA that does nothing except count time steps while the decoder does all the actual computation. Hudcova walks through this failure mode in some detail, because getting the definition right is what makes the subsequent negative results possible.

Global universality is a strictly stronger demand: a cellular automaton must be able to simulate every other cellular automaton of the same dimension, operating on the infinite grid. Game of Life, famously, can do this — you can construct a configuration of Game of Life that, at a sufficiently zoomed-out scale, replicates the dynamics of an entirely different cellular automaton, including Game of Life itself.

Matthew Cook's proof of Rule 110's computational universality is the most striking illustration of what local universality can look like. Rule 110 is an elementary one-dimensional cellular automaton with only eight rules — an observation documented in the technical literature on elementary cellular automata — yet it is capable of universal computation. Hudcova attributes much of that apparent magic to the encoders and decoders, which in Cook's original construction required exponential slowdown and were only later tightened to polynomial time. The universality is real; the compactness is partially an artifact of what the translation layers are permitted to do.

Hudcova also presents a new result connecting these classes to topological dynamics: for every Turing machine, there exists a cellular automaton that can locally simulate it while having zero topological entropy, and zero topological entropy rules out global universality. The classes are strictly nested, separated by measurable dynamical properties.

The main result: computation is not sufficient for life

With these definitions in hand, Hudcova's central theorem becomes statable. She introduces a minimal criterion for self-replication she calls the local self-replicating condition: a cellular automaton satisfies it if it contains a pattern with non-trivial temporal dynamics (not just a static crystal) that produces a growing number of disjoint copies against a computationally reasonable background. Bill's loop — a compact self-replicating structure in a well-known cellular automaton — satisfies this condition. Crystal growth, with no internal temporal variation, does not.

The theorem: there exists a locally universal cellular automaton that does not satisfy even this minimal self-replication condition.

The construction is a one-dimensional CA that accurately mimics Turing machine computation when a single head is present on the tape, but when multiple heads appear, they partition the grid into territories that prevent any communication or cooperation. The only active elements in the grid — the heads — cannot interact, so they cannot participate in replication. The system computes, in the full Turing-complete sense, but it cannot reproduce.

"Even if in the future we come up with more stringent criteria for self-replication," Hudcova notes, "this result would still hold, as our example would also rule out these future more stringent versions."

The result establishes that the class of universal self-replicating systems — those that are both locally universal and satisfy the replication condition — is a proper subset of locally universal systems. Computing is necessary for neither, and neither is sufficient for the other.

What remains open

An audience member during the talk pushes on a question that gets at something important: if you randomly erase some of the self-replicating loops in a system, do they get refilled? Hudcova's answer is that individual loops are typically fragile to perturbation, but that loops will keep trying to replicate as long as space is available — and that robustness to perturbation would be a natural criterion for making the self-replication definition more stringent.

Michael Levin, whose group hosted the talk, presses further: if the existence of one loop is contingent on the existence of others, "there is no self there. They're not independent."

That exchange points toward the genuinely hard question the formalism hasn't yet reached. Hudcova is explicit that a complete characterization of non-trivial self-replication remains open. The results so far establish a floor, not a ceiling. The hierarchy of increasingly stringent criteria she calls for — incorporating noise, continuous media, perturbation robustness — is, at this point, a research program rather than a result.

What the work does accomplish is something that sounds modest but is actually quite difficult: it makes the question precise enough that a negative answer is possible. Before you can prove that computation is not sufficient for life, you need definitions of both that are tight enough to be falsifiable. That, more than any particular theorem, may be the contribution that compounds.

Barbora Hudcova is a postdoctoral researcher at EPFL. The talk was delivered at the Allen Discovery Center at Tufts University.

— Priya Sharma, Science & Health Correspondent