Skip to content

Cellular Automata and Artificial Life

Abstract

A cellular automaton is a grid of cells, each obeying the same simple rule about its neighbors. From this austere setup came some of computing’s strangest results: John von Neumann designed a self-reproducing machine in it before the structure of DNA was known, John Conway’s Game of Life escaped from a 1970 magazine column to colonize the world’s mainframes, and Christopher Langton used it to found a discipline, artificial life, that promised digital organisms and briefly believed its own promise. The field produced Turing-complete one-dimensional rules, evolving computer programs with parasites, a lawsuit over a mathematical proof, and a 1,197-page book claiming all of science should be rebuilt on it.

John Horton Conway 2005
John Horton Conway in 2005. He invented the Game of Life with pen, paper, and Go boards, and spent the rest of his career mildly annoyed that it was the first thing anyone asked him about. Image: Thane Plambeck, CC BY 2.0, via Wikimedia Commons.

A Machine That Builds Itself

The field began with a question that sounds biological: can a machine build a copy of itself, including the machinery for making further copies? John von Neumann posed it in lectures from 1948 onward, and his colleague Stanislaw Ulam suggested the medium: forget gears and arms, model the machine as patterns of states on an infinite grid of cells, each cell updating in discrete time steps according to a fixed rule about its neighbors. Ulam had been playing with such lattice games at Los Alamos; the abstraction stripped away every engineering nuisance and left the pure logic of construction.

Von Neumann worked out a 29-state cellular automaton containing a universal constructor: a configuration that reads a description tape, builds whatever the tape describes, then copies the tape into the new machine. If the tape describes the constructor itself, the machine reproduces. The design separates the description used two ways, first as instructions to execute, then as data to copy verbatim. Watson and Crick found the same split in the cell in 1953, transcription and replication, five years after the lectures. Von Neumann died in 1957 with the manuscript unfinished; Arthur Burks completed and published it as Theory of Self-Reproducing Automata in 1966. The construction was so intricate that nobody ran it: a complete implementation of a von Neumann-style self-reproducer waited until Renato Nobili and Umberto Pesavento in 1995, using a 32-state extension.

Codd’s Eight States

The first simplification came from an unexpected name. Edgar F. Codd, the IBM researcher later famous for the relational database (see Edgar Codd and the Relational Model), wrote his University of Michigan doctoral work on cellular automata under Burks’s influence and published it in 1968 as the book Cellular Automata. Codd showed that von Neumann’s 29 states were far more than necessary: an 8-state automaton could support both universal computation and universal construction. His design wrapped signal paths in sheathed “wires” of cells, a style every successor borrowed.

Codd’s machine shared the fate of von Neumann’s: too large to run on the hardware of its day, it remained a paper construction for four decades. Tim Hutton finally built a working configuration in 2009, correcting minor errors in the 1968 specification along the way. Codd himself moved on to databases within two years, making Cellular Automata one of the odder first acts in computer science.

The Game of Life

Gosper Glider Gun
The Gosper glider gun, found in November 1970 by Bill Gosper’s MIT group. It fires a new glider every 30 generations, proving Life patterns can grow without limit. Image: Bryan.burgers, public domain, via Wikimedia Commons.

While the constructors gathered dust, a Cambridge mathematician made cellular automata famous by accident. John Horton Conway wanted the simplest possible rule that produced unpredictable behavior, and tuned it by hand in the late 1960s, pushing counters around Go boards in the Cambridge mathematics common room. The result, the Game of Life, needs one sentence: a live cell survives with two or three live neighbors, a dead cell comes alive with exactly three, everything else dies or stays dead.

Martin Gardner presented Life in his Scientific American “Mathematical Games” column in October 1970, and it detonated. Conway had conjectured that no pattern could grow forever and offered $50 to anyone who settled the question by the end of 1970. Bill Gosper’s group at MIT collected in November with the glider gun, a pattern that emits an endless stream of gliders, small spaceships that crawl across the grid. The gun was more than a prize-winner: streams of gliders can be collided to build logic gates, and from there wires, memory, and entire processors. Life is Turing complete; anything computable can in principle be computed by dots on its grid. Gosper later contributed HashLife (1984), an algorithm exploiting the grid’s self-similarity to simulate patterns for trillions of generations, and programmers everywhere contributed the countless machine cycles Life consumed on time-shared systems, to the documented irritation of their administrators. Writing Life in as little code as possible became a standard stunt; APL programmers managed it in one line.

Conway had mixed feelings about his hit. He was proud of the construction but came to resent that a recreational rule overshadowed his work in group theory and his invention of surreal numbers. He died on 11 April 2020 in New Brunswick, New Jersey, of COVID-19, three days after developing symptoms; the obituaries led with Life anyway.

Langton and the Naming of a Field

Langtons Loops Colony
A colony of Langton’s loops. Each loop replicates until it runs out of room; the dead loops in the center remain as a growing “coral reef” of the colony’s history. Image: Ferkel, public domain, via Wikimedia Commons.

Christopher Langton found the thread von Neumann had left and pulled. A University of Michigan graduate student in the tradition of Burks and John Holland, he asked what self-reproduction looked like if you dropped the requirement of universal construction: not a machine that can build anything, only one that can build itself. In 1984 he modified Codd’s rule set into Langton’s loops, self-replicating structures of 86 cells where Codd’s design had needed millions. A loop is a sheathed ring of circulating instructions with a construction arm; the instructions read “build a loop,” and so it does, again and again, until the colony fills the available space.

Langton, then at Los Alamos National Laboratory, gave the enterprise a name and a founding event: the “Interdisciplinary Workshop on the Synthesis and Simulation of Living Systems” at Los Alamos in September 1987, remembered as the first Artificial Life workshop. The manifesto was explicit: biology studies life as it is; artificial life studies life as it could be, in any medium. His theoretical contribution, the lambda parameter (1990), measured where a cellular automaton rule sits between frozen order and boiling chaos, with computation and life-like behavior clustering at the phase transition, a region he called the edge of chaos. The phrase escaped the paper and became a management-book cliché, which is one measure of the field’s cultural moment. Langton also left a small puzzle that outlived his career, Langton’s ant (1986), two rules on a grid whose long-term highway-building behavior remains unproved in general. He moved to the Santa Fe Institute, and left research entirely in the late 1990s.

Digital Evolution

The ALife program needed more than self-copying; it needed variation and selection. The mathematical groundwork was older: John Holland, in Adaptation in Natural and Artificial Systems (1975), had formalized the genetic algorithm, breeding candidate solutions through mutation, crossover, and selection, an idea that spent two decades as a Michigan specialty before becoming a standard optimization tool.

The Los Alamos generation set evolution loose inside the machine. The ecologist Thomas Ray built Tierra (1991), a virtual computer whose inhabitants are self-replicating machine-code programs competing for CPU time and memory. Nobody defined a fitness function; survival was the only score. Tierra promptly evolved parasites, short programs that borrowed the copy routines of their neighbors, then hyper-parasites that exploited the parasites, a miniature ecology emerging from 80 instructions. Avida (1993), developed at Caltech and later Michigan State, domesticated the approach for controlled experiments; a 2003 Nature paper used it to watch complex functions evolve step by step. On the graphics side, Craig Reynolds showed in 1986 that flocking needs no leader: his boids follow three local rules (separation, alignment, cohesion) and a flock emerges, a technique that animated the bat swarms and penguin armies of Batman Returns (1992). Karl Sims’s evolved virtual creatures (1994) closed the loop, breeding jointed block-bodies and their neural controllers together until swimmers, walkers, and one memorable arm-flailing hopper emerged without anyone designing them.

Wolfram’s Simple Programs

Stephen Wolfram, already met in this encyclopedia as the creator of Mathematica (see Computer Algebra Systems), gave cellular automata their systematic natural history. In papers beginning 1983 he surveyed the 256 elementary cellular automata, one-dimensional rules on two states, and sorted all CA behavior into four classes: uniform, periodic, chaotic, and a fourth class of localized structures interacting in complicated ways, the class where computation lives. Rule 30 produced such convincing chaos from one black cell that Wolfram used it as the random number generator in Mathematica. Rule 110, a Class 4 rule, he conjectured in 1985 to be Turing complete.

His young employee Matthew Cook proved it, showing Rule 110 emulates cyclic tag systems. Then the story turned corporate: when Cook presented the result at a Santa Fe conference in 1998, Wolfram Research sued, claiming his nondisclosure agreement reserved the proof for Wolfram’s forthcoming book, and obtained a court order keeping the paper out of the proceedings. The proof appeared under Wolfram’s name-brand first, in A New Kind of Science (2002), with credit to Cook; Cook’s own paper finally ran in Complex Systems in 2004. Universality in so small a rule is a genuinely striking result, and the injunction against its author remains one of the stranger events in the sociology of mathematics.

A New Kind of Science itself, 1,197 self-published pages produced in a decade of seclusion, claimed far more: that simple programs, not equations, are the right foundation for physics, biology, and everything else, governed by a “principle of computational equivalence.” It sold well and reviewed badly. Scott Aaronson and Cosma Shalizi noted that the central results were either old, minor, or Cook’s; Steven Weinberg found the physics unmotivated. The book’s lasting effect was smaller than its ambition and larger than its critics conceded: a generation of readers met cellular automata through it.

Dead End: Life, but Not as We Know It

The strong claim of 1987-era artificial life was that digital organisms would be alive, that life is a process indifferent to its substrate, and silicon would host it as well as carbon. The claim aged poorly. The evolutionary biologist John Maynard Smith, though himself interested in the simulations, heard the field described in terms he distilled in 1994 as “fact-free science”: elegant models, no organisms, no data. Tierra’s ecology, thrilling at first, hit a ceiling; later analyses by Mark Bedau and Russell Standish found that Tierra-like systems stop generating novelty, while the open-ended creativity of natural evolution stayed out of reach. Dedicated CA hardware fared no better: Tommaso Toffoli and Norman Margolus’s CAM machines at MIT, built in the late 1980s to make cellular automata a computing substrate, remained laboratory curiosities. By the early 2000s the ALife institutes had shrunk, Langton was gone from research, and the journals carried on quietly without the manifesto.

What survived was the toolbox, detached from the ideology. Genetic algorithms became routine optimization; boids-style agent rules became crowd simulation, swarm robotics, and agent-based modeling in economics and epidemiology; the digital-organism platforms became instruments for evolutionary biology rather than replacements for it (see The Rise of Artificial Intelligence for the parallel story of neural networks, which crashed and returned). The strangest postscript is wet: the xenobots of 2021, cell clusters designed by evolutionary algorithms that assemble copies of themselves from loose cells, brought the field’s founding question, whether construction and reproduction can be engineered, back into biology, where von Neumann had found it.

📚 Sources