Odd AlmanacSearch

Cellular automata and emergent complexity

Self-reproduction, emergence and the mathematical reach of tiny programmes.

5 entries · 2 sections

Jump to a section ↓More in Machines & futures →
John H. Conway at a mathematics conference
John H. Conway at a combinatorial game theory conference in Banff, June 2005. Thane Plambeck · CC BY 2.0

Cellular automata tie several threads to documented mathematics: von Neumann’s replication question, Conway’s emergent patterns, Wolfram’s complexity programme and Cook’s universality proof. These results concern what formal systems can do. Claims about conscious experience, alien visitors or a digitally constituted universe require additional arguments and evidence.

Five cells and a moving pattern

A glider returns to the same shape after four generations, shifted one cell diagonally. Its apparent movement emerges from local updates; there is no separate instruction telling the whole pattern to travel.

Generation 0
Generation 1
Generation 2
Generation 3
Generation 4

Computed illustration of Conway’s Game of Life. A live cell survives with two or three live neighbours; an empty cell becomes live with exactly three. All cells update together. Bright squares are live. This demonstrates a mathematical pattern, not evidence of consciousness or a physical universe made of cells.

Rules and original description: The fantastic combinations of John Conway’s new solitaire game life (external source, opens a new tab)

Construction and emergence

Von Neumann’s question about self-reproducing automata and Conway’s Life, where elaborate patterns follow from compact local rules.

John von Neumann during his Los Alamos period.
John von Neumann during his Los Alamos period. Los Alamos National Laboratory · LANL attribution permission

Research & assessmentOriginal collected work · 1966 volume; 1948–49 lectures

Von Neumann · Reproduction needs a description

Von Neumann’s question of how an automaton could build another, with a description used as instructions and copied onward.

Von Neumann asked how an automaton could construct another automaton, including the information needed for further reproduction. A useful distinction is between a constructor using a description as instructions and a copying process passing that description onward. Burks dates the precursor Hixon lecture to September 1948 and five Illinois lectures to December 1949; the edited volume appeared in 1966. This is the mathematical ancestry of artificial-life and self-reproducing-machine discussions already present in the atlas, and it concerns organisation and replication, not evidence that a machine has subjective experience.

The early kinematic model and later cellular model are stages of the work, not interchangeable completed machines.

Read the scanned book — PDF, 35 MB (external source, opens a new tab)
Source details & what was checked
John H. Conway at a mathematics conference
John H. Conway at a combinatorial game theory conference in Banff, June 2005. Thane Plambeck · CC BY 2.0

History & recordContemporary primary exposition · October 1970

Conway · Life from local rules

Gardner’s 1970 introduction to Conway’s Life: simple neighbour rules yield stable patterns, oscillators and moving gliders, without intention in any cell.

Gardner introduced Conway’s Life to Scientific American readers in October 1970. Each square is alive or dead and consults its eight neighbours: a living square survives with two or three; an empty square becomes alive with exactly three; all updates occur simultaneously. Repeated application produces stable arrangements, oscillators and moving gliders: patterns maintained through changing cells, not tiny agents receiving separate movement instructions. The documented connection to this atlas is emergence: elaborate organised behaviour can follow from compact rules without inserting intention into each component.

The article’s growth conjecture and prize describe the state of knowledge in October 1970; do not present them as current open problems.

Read free source (external source, opens a new tab)
Source details & what was checked
Back to sections ↑

Complexity and computation

Wolfram’s classification of cellular automata and Cook’s Rule 110 proof, separating what was proposed from what was proved about universal computation.

Portrait of a bald man in glasses and a blue striped shirt in front of an orange wall
Stephen Wolfram, publicity photograph supplied by his staff, 2008. Later photograph; the cited papers date from 1983 and 1984. Stephen Wolfram's PR team / Stephen Faust · CC BY-SA 3.0

Research & assessmentOriginal research exposition · 1983

Wolfram · Complexity without complicated components

Wolfram’s 1983 account of cellular automata as discrete models, where an exclusive-or rule grows a triangular self-similar pattern from one seed.

Wolfram’s 1983 account studies cellular automata as discrete mathematical models: finite cell states, local deterministic updates and repeated time steps. Even a rule based on the exclusive-or of neighbouring cells creates a self-similar triangular pattern from a single seed. He also examines structure emerging from disordered initial conditions. The associated research programme asks which mechanisms are shared across complex natural systems, not whether every natural object literally runs this particular rule. This supplies a concrete scientific link between computation, pattern formation and the atlas’s broader interest in emergent organisation.

Companion paper: Statistical Mechanics of Cellular Automata, Reviews of Modern Physics 55, 601–644 (1983); official bibliography verified.

Read free source (external source, opens a new tab)
Source details & what was checked
Editorial illustration: a grid of cells, some filled
Editorial illustration · Z13 visual study

Research & assessmentOriginal theoretical research · 1984

Four behaviours, with universality still a hypothesis

Wolfram’s 1984 four behavioural classes of one-dimensional automata, whose fourth was proposed as probably universal: a hypothesis, not a proof.

In 1984 Wolfram presented evidence for four qualitative behavioural classes in one-dimensional cellular automata. His abstract compares three to fixed outcomes, cycles and chaotic behaviour, and identifies a fourth, with complex structures, as a candidate for universal computation. Preserve the historical wording: the fourth class was proposed as probably universal, not every complex-looking automaton proved capable of arbitrary computation. Beside singularity discussions, this matters: visible complexity, computational capacity and intelligence are separate properties. A classification of mathematical dynamics supplies no date or mechanism for an awakening.

Based on the original abstract and author bibliography; full paper was not accessible in this pass.

Read free PDF (50 MB) (external source, opens a new tab)
Source details & what was checked
  • Stephen Wolfram / Physica D 10, 1–35 · 1984
    Publisher-indexed abstract read; author bibliography confirms date. Full publisher and author PDF fetches failed. Four-class evidence and class-IV universality conjecture are stated at abstract level, not a checked theorem. Access update, 20 October 2026: Author-hosted original50.3MB PDF downloaded completely with HTTP200; pypdf read37PDFpages and correct title, introduction and mid-paper text. Large download; browser PDF viewer remained blank, so verification is file/content, not rendered-browser proof.
    Universality and Complexity in Cellular Automata (external source, opens a new tab) · In the source library
Editorial illustration: a circuit chip with pins
Editorial illustration · Z13 visual study

Research & assessmentOriginal mathematical universality proof · 2004

Cook · Rule 110 really can compute

Cook’s 2004 proof that Rule 110, a two-state rule on a line, is computationally universal, given suitable encoding, space and time.

Cook’s 2004 paper proves computational universality for Rule 110, an elementary automaton with two states and nearest-neighbour updates on a line. Carefully arranged propagating patterns can implement a universal computation through encoded tag-system operations. A simple rule can therefore support arbitrary algorithms when supplied with suitable encoding, space and time; it does not mean every random initial pattern is an intelligent programme. For the atlas, this is a rigorous bridge between simple local dynamics and general computation. It neither establishes consciousness nor demonstrates that physical spacetime is a cellular automaton.

The universality construction uses prepared backgrounds and encodings. Abstract computational resources should not be mistaken for a finite physical machine’s capabilities.

Read free source (external source, opens a new tab)
Source details & what was checked
Back to sections ↑

Across the Cabinet

Strange overlaps with this chapter

Follow another thread

Related chapters, with each source and interpretation kept in its own context.

Strange placesWeird websitesPocket worlds, mysterious libraries, inexplicable doors and quiet windows onto other things.Machines & futuresMachines & historyThe postwar dates, the recovered-technology allegation, and three different von Neumann ideas.