State
A cell is either 0 (empty) or 1 (filled). These are the elements of the set S = {0, 1}.
MATHEMATICS · INTERACTIVE FIELD GUIDE
Discrete worlds
Start with a cell. Give it a rule. Watch a world unfold.
Explore sets, logic, counting, graphs, and proof through cellular automata. No calculus required.
01 / EXPERIMENT
One rule. Many possible worlds.
Each horizontal row is a world at one moment. Time runs downward. Change a rule or flip an output below to rebuild the history.
The rule table · tap an output to change it
Read inputs from 111 to 000. The eight output bits form the rule number in binary.
Space runs left to right · time runs downward
02 / DEFINE
A world built from separate pieces
Discrete mathematics studies distinct objects and the relationships between them: bits, integers, sets, networks, and sequences. A cellular automaton brings these ideas together. Each cell has a state; a local rule determines its next state; time advances in whole steps.
Neighbourhood
A cell reads a small group around it. In our one-dimensional world, that is left, centre, and right.
Update
All cells compute their next state from the same old generation, then change together. This is a synchronous update.
03 / CONNECT
The discrete-math toolkit
The patterns are an entry point. These five ideas explain what the machine is doing.
01 / Sets
A set is a collection of distinct elements. Let A be the positions of filled cells. Tap the cells to change A. The symbol |A| counts its elements.
02 / Logic
A logical operation maps truth values to a truth value. With 0 = false and 1 = true, rule 90 is left XOR right: the next cell is 1 exactly when the two neighbours differ.
03 / Counting
For k binary inputs, there are 2ᵏ possible input patterns. A rule independently chooses 0 or 1 for every pattern, so there are 2^(2ᵏ) possible rules. Do not confuse inputs with rules.
04 / Graphs and functions
A graph has vertices (cells) and edges (neighbour relationships). The local rule is a function f: S³ → S. Applying it everywhere gives a global function F that takes one whole configuration to the next.
xᵢ(t + 1) = f(xᵢ₋₁(t), xᵢ(t), xᵢ₊₁(t))
Three states at time t determine one state at time t + 1. Dependencies reach at most one cell farther per step.
05 / Proof and induction
A picture suggests a claim; a proof explains why it must hold. Suppose f(0,0,0) = 0 and initially only the centre is filled. After t steps, every filled cell lies at most t positions from the centre (before wrap-around matters).
- Base case: at t = 0, only the centre is filled.
- Inductive step: assume the claim at time t. Any cell farther than t + 1 has three zero inputs, so it remains zero. Therefore the claim also holds at t + 1.
The condition matters: rule 1 has f(0,0,0) = 1, so empty regions light up immediately. Try it above.
04 / GO TWO-DIMENSIONAL
From a line to a living grid
Conway’s Game of Life uses eight surrounding neighbours. A dead cell is born with exactly 3 live neighbours. A live cell survives with 2 or 3. Every other cell is dead in the next generation. The centre does not count as its own neighbour.
32 × 20 cells. Click or tap to toggle a cell; editing pauses time. For keyboard editing, choose a row and column below. Boundary changes restart the selected pattern.
Inspect a local update
Toggle the eight neighbours and the centre. Predict the centre’s next state, then compare with the result.
05 / REASON
Small rules, serious questions
Cellular automata connect discrete mathematics to computation and dynamical systems. A configuration is a state, the rule is an algorithm, and repeated updates form a sequence. Rich behaviour can emerge without a central controller.
Why a finite world eventually repeats
An N-cell binary board has 2ᴺ configurations. A deterministic rule assigns exactly one successor to each. Among 2ᴺ + 1 successive configurations, two must be equal (the pigeonhole principle). From that point the future repeats. The cycle may have length 1. This argument applies to our finite boards with a fixed boundary choice; it does not prove repetition on an infinite grid.
What a simulation can—and cannot—tell you
A finite run can reveal a pattern, disprove a universal claim with a counterexample, or suggest a conjecture. It cannot by itself establish that a pattern persists forever. These binary grids are mathematical models, not literal models of biological life.
Check your understanding
Why are there 256 elementary rules rather than 8?
There are 8 possible three-bit neighbourhoods. For each one, choose one of 2 outputs independently: 2⁸ = 256.
Would updating the grid in place give the same automaton?
Not generally. Later cells could read already-changed neighbours. Synchronous updates require a separate next-generation grid.
Does a random starting pattern make the update rule random?
No. Randomness chooses the initial state. Once that state and the rule are fixed, the subsequent evolution is deterministic.