Computational Life: How Well-formed, Self-replicating Programs Emerge from Simple Interaction
Blaise Agüera y Arcas, Jyrki Alakuijala, James Evans, Ben Laurie, Alexander Mordvintsev, Eyvind Niklasson, Ettore Randazzo, Luca Versari
cs.NE, cs.AI
2024-06-27
Random programs in minimal languages left to execute and overwrite each other spontaneously develop self-replicators, no fitness function needed; SUBLEQ is a counterexample.
Origin-of-life research lives mostly on chemical substrates: RNA worlds, autocatalytic networks. On computational substrates, the question of how life gets started has barely been touched experimentally. The classic artificial-life systems, Tierra and Avida, both begin from a hand-written "ancestor" replicator, which skips the hard part entirely: the transition from a pre-life state with no replicators to one where they dominate. Earlier pre-life experiments such as Coreworld did observe spontaneous replicators, but attributed them to random initialization or background mutation. Google's Paradigms of Intelligence team, with James Evans from the University of Chicago, set out to nail the attribution: with no fitness function at all, what actually drives random programs to acquire self-replication?
The main apparatus is a primordial soup, a variant of Fontana's 1991 Turing gas: 2^17 programs of 64 bytes each, randomly initialized. Every epoch a random ordered pair is concatenated, executed, then split back into two 64-byte strings and returned to the pool. The crucial design choice is that the instruction tape and the data tape are the same, so execution inevitably overwrites both participants, and mutual overwriting is the only way programs interact. The primary language is BFF, an extension of Brainfuck: input/output streams are replaced by copy operations between two heads, giving 10 valid instructions out of 256 byte values, with the rest usable as data.
Two instruments detect the state transition (a replicator taking over the soup):
| Setting | Result |
| BFF soup, 0.024% mutation rate | 40% of runs transition within 16k epochs |
| Zero mutation, fixed pairing pattern | 50%, if anything higher |
| 128-epoch runs (tests random initialization) | 3 transitions out of 1000 |
| Seeded with one hand-written replicator, 128 epochs | 22% take over |
| Forth soup | Nearly all runs transition within 1k epochs |
| SUBLEQ / RSUBLEQ4 | No spontaneous emergence after billions of executions |
The comparisons pin down the cause. Short runs transitioning only 3 times in 1000 rules out lucky initialization. The zero-mutation, fixed-pairing variant stops total system entropy from growing yet transitions more often than the default, which rules out background mutation. What remains is programs rewriting each other. The case study backs this: the first replicator is born in a messy rewrite event, gets overwritten itself, and survives through its copies; a "zero-poisoning" dip follows (the first-generation replicator cannot overwrite zero bytes), and a more robust [<,}] family eventually takes over. Real instruction sets reproduce the pattern: on Z80, stack-based replicators sweep the 2D grid first, then get displaced by variants exploiting the LDIR/LDDR block-copy instructions; on the 8080, replicators are always two repeated bytes (e.g. 01 c5) and no looping variant ever appeared. In the long-tape Forth setting, looping "good" replicators show up within about 60 seconds, or 180 billion instructions, at roughly 3·10^9 instructions per second. Forth transitions far faster than BFF, partly because it admits a trivial one-byte replicator (instruction 0C). The counterexample is SUBLEQ: the shortest hand-written replicator is 60 bytes, the modified RSUBLEQ4 still needs 25, seeding works, but random initialization stays uniform noise forever.
This is among the first systematic attempts to explain how life starts on a computational substrate, and the value is threefold. The attribution is clean: self-modification is shown to be the main driver, something no prior computational-substrate study established. The instruments are reusable: tracer tokens and high-order entropy do not depend on the language and apply to any open-ended evolving system. And the counterexample suggests the length of the shortest viable replicator may be the variable that predicts whether a language can harbor life, a concrete entry point for a theory. For anyone working on open-ended evolution, or worried about self-replication risk in AI systems, this is a ready-made testbed; the code is open source with CUDA support.
The authors' own list: the single-step autocatalysis framing does not cover multi-step autocatalytic sets, and judging replication by a perfect 64-byte self-copy misses functional replicators that copy with an offset, while substring-level detection is computationally intractable, so the evidence mixes case studies with aggregate metrics. Beyond that: 3 transitions in 1000 short runs shows lucky initialization is rare but does not fully rule out an initialization contribution; the SUBLEQ counterexample comes with only a preliminary length-based explanation and no theory; high-order entropy approximates Kolmogorov complexity with brotli while the experiments use a pseudo-random generator, so true K is capped by the generator's program size, a caveat the paper touches in one sentence; and there is no sensitivity analysis on the transition threshold (complexity ≥ 1), so how robust the headline 40% figure is to that threshold remains unknown.