BTT Mathematics / Primary Mathematics Learning Hub / Cellular Automata
A cellular automaton is a collection of cells that update their states using the same local rule. The rule is simple and repeated everywhere, yet the global pattern can become surprisingly structured.
A one-dimensional binary automaton may use cells in state 0 or1. At each time step, every cell calculates its new state from a specified neighborhood in the old generation. All updates then occur together. This is called synchronous updating.
This guide uses two explicit systems:
1. A finite one-dimensional version of Rule 90, where a cell’s new value is the XOR of its left and right neighbors. Equal neighbor values give0; different neighbor values give1. Cells outside the finite row are treated as0.
2. Conway’s Game of Life, a two-dimensional binary automaton used here only for small, hand-checkable patterns.
This guide is Primary Mathematics enrichment. It connects Regularity in Repeated Reasoning, Algorithms, Flowcharts and Decision Trees, Fractals, Self-Similarity and Scaling Patterns and state-transition reasoning.
These automata are optional enrichment rather than universal Primary syllabus requirements. Every rule needed for the exercises is stated locally.
Local rules · Rule 90 · State spaces · Game of Life · Still lifes and oscillators · Emergent patterns · 24 questions · Worked answers
1. Local rules act everywhere at the same time
A local rule reads a cell’s neighborhood in generation t and determines its state in generation t+1. The new generation should be calculated from the old generation, not from a mixture of already-updated and not-yet-updated cells.
Worked example A: Why synchronous updating matters
Suppose a row is updated left-to-right and a newly changed left cell is immediately used to update the next cell. That is a different dynamical system from a cellular automaton whose entire next row is based on the previous row.
Worked example B: Binary state count
A row of n binary cells has 2ⁿ possible states. A five-cell row has32 states; a ten-cell row has1024.
Worked example C: Deterministic rule
If the same state is presented twice under the same deterministic update rule and boundary convention, the next state is the same both times.
Worked example D: State-transition graph
Each complete row can be treated as a vertex. The update rule points from each state to exactly one next state. Repeated evolution traces a directed path through the finite state graph.
2. Rule 90: new cell = left XOR right
For Rule 90, ignore the center cell when computing its own next state. Use only the old left and right neighbors:
0 XOR 0 = 0
0 XOR 1 = 1
1 XOR 0 = 1
1 XOR 1 = 0
In our finite examples, cells beyond the left and right ends are fixed at0.
Worked example E: One seed in seven cells
Start: 0001000.
Generation1: 0010100.
For the cell immediately left of the center, its old neighbors are0 and1, so it becomes1. The center’s old neighbors are0 and0, so it becomes0. Symmetry gives the corresponding right-side1.
Worked example F: Next generation
From0010100, Rule 90 gives 0100010.
Worked example G: Third generation
From0100010, the next row is 1010101.
Worked example H: Fixed-zero boundaries change the later evolution
From1010101, every cell sees equal left/right neighbors under the fixed-zero convention, so the next row is 0000000. On an infinite line, there would be cells beyond the seven-cell window, so the visible evolution would differ.
3. Finite deterministic automata eventually repeat
A finite n-cell binary automaton has only2ⁿ possible complete states. If the rule is deterministic and evolution continues forever, eventually some state must repeat.
Once a state repeats, the future after that state also repeats, because a deterministic state always has the same successor. The system therefore eventually enters a cycle.
Worked example I: Absorbing zero state
Under finite Rule 90 with fixed-zero boundaries, the all-zero row maps to itself. It is a fixed point.
Worked example J: Fixed point
A state S is a fixed point when update(S)=S. Repeating the rule produces no further visible change.
Worked example K: Periodic orbit
If A→B→A, the states form a period-2 cycle. The complete system alternates forever between the two states.
Worked example L: Pigeonhole reasoning
With only32 possible states in a five-cell binary automaton, a trajectory containing33 visited states must repeat at least one state. This does not say the period is32; only that repetition must have occurred.
4. Game of Life uses the eight neighboring cells around each square
In the Game of Life, each cell is either alive or dead. Every update is synchronous.
Live cell: survives if it has2 or3 live neighbors; otherwise dies.
Dead cell: becomes alive if it has exactly3 live neighbors; otherwise remains dead.
Worked example M: Single live cell
It has zero live neighbors, so it dies in the next generation.
Worked example N: Two adjacent live cells
Each live cell has only one live neighbor, so both die. No surrounding dead cell has exactly three live neighbors, so the next generation is empty.
Worked example O: Live cell with two neighbors
It survives.
Worked example P: Live cell with four neighbors
It dies from overpopulation under the stated rule.
Worked example Q: Dead cell with exactly three live neighbors
It becomes alive in the next generation.
5. Simple local rules can create stable and periodic global patterns
Worked example R: 2×2 block
Four live cells arranged as a solid2×2 block form a still life. Each live cell has exactly three live neighbors, so all survive. Every surrounding dead cell has fewer than three live neighbors that would create a new birth in the relevant positions. The block remains unchanged.
Worked example S: Blinker
Three live cells in a horizontal row form a period-2 oscillator. After one step they become three vertical live cells centered at the same middle cell. After the next step they return to horizontal.
Worked example T: Period
A pattern has period p when p is the smallest positive number of generations after which the complete pattern repeats. The blinker has period 2.
Worked example U: Still life as period1
A stable block may also be described as period1 because it repeats after every update.
6. Emergence means global structure is produced by repeated local interactions
No cell in Rule 90 is instructed to draw a large triangle. No Game-of-Life cell knows whether the global pattern is a blinker. Each cell applies only its local rule.
Worked example V: Rule 90 and self-similarity
On a sufficiently large or infinite line, repeated Rule 90 updates from a single seed form a triangular pattern related to the Sierpiński triangle. Large-scale structure emerges from repeated XOR neighborhoods.
Worked example W: Boundary conditions matter
Fixed-zero, wraparound and infinite boundaries can produce different futures from the same visible starting row. The update rule is not fully specified until the boundary convention is also known.
Worked example X: Local simplicity does not imply global simplicity
A rule table may contain only a few cases, while the long-run state path can contain fixed points, cycles, expanding patterns or other complex behavior.
7. Practice: 24 original questions
Questions 1–8: Rule 90
1. Under XOR, what is0 XOR0?
2. What is0 XOR1?
3. What is1 XOR0?
4. What is1 XOR1?
5. Starting from0001000, find the next Rule-90 row using fixed-zero boundaries.
6. Find the next row after0010100.
7. Find the next row after0100010.
8. Find the next row after1010101 under the same finite boundary rule.
Questions 9–16: States and Game of Life
9. How many states does a five-cell binary row have?
10. How many states does an n-cell binary row have?
11. Why must a finite deterministic automaton eventually repeat a state if run forever?
12. What is a fixed point?
13. In Game of Life, what happens to a single isolated live cell?
14. What happens to two adjacent live cells with no others nearby?
15. Does a live cell with two live neighbors survive?
16. What happens to a dead cell with exactly three live neighbors?
Questions 17–24: Patterns and emergence
17. Does a live cell with four live neighbors survive?
18. What happens to a dead cell with only two live neighbors?
19. What kind of pattern is a2×2 live block?
20. What happens to a three-cell horizontal blinker after one step?
21. What is the blinker’s period?
22. Why must all cells in one generation be updated from the old generation rather than sequentially?
23. Why can different boundary conditions change the future of the same finite row?
24. Explain “emergent pattern” in the context of cellular automata.
8. Worked answers
Answers 1–8
1. 0.
2. 1.
3. 1.
4. 0.
5. 0010100.
6. 0100010.
7. 1010101.
8. 0000000.
Answers 9–16
9. 32 states. 2⁵.
10. 2ⁿ.
11. There are finitely many states. An infinite trajectory must revisit one; determinism then repeats the future from that state.
12. A state that maps to itself after one update.
13. It dies.
14. Both die and no new cell is born nearby.
15. Yes.
16. It becomes alive.
Answers 17–24
17. No. It dies.
18. It remains dead.
19. A still life, equivalently a period-1 pattern.
20. It becomes a vertical line of three live cells.
21. 2.
22. Sequential use of newly updated cells changes the rule. A cellular-automaton generation is defined by applying the same rule to the same old state everywhere.
23. Edge cells see different neighbors under fixed-zero, wraparound or infinite conventions, so their updates and later propagated effects differ.
24. Large-scale organization or repeated behavior arises from many cells repeatedly following a simple local rule, even though no individual cell encodes the global pattern.
9. Teaching and transfer
If a learner changes cells one at a time and immediately reuses the new values, draw an “old row” above a blank “new row.” Every calculation must read only from the old row.
When Rule 90 feels like magic
Write the four XOR cases beside the row. Each new cell then becomes a small local calculation rather than a guessed pattern.
When long-run behavior is confused with one step
Separate the update rule from the trajectory. The rule describes one transition; repeated application produces the history.
When Game-of-Life patterns are memorized without checking
Count live neighbors cell by cell. Still lifes and oscillators are consequences of the local rules, not exceptions to them.
When boundaries are ignored
State the boundary convention before evolving a finite row. Missing that condition can make two correct-looking solutions disagree.
Connect to state transitions
Like the Tower of Hanoi, a finite automaton can be viewed as movement through a state graph. The difference is that a deterministic automaton has one prescribed successor from each state, while the Tower usually offers several legal moves.
Continue through this enrichment collection
For recursive state paths, use Tower of Hanoi, Recursion and State Transitions. For adjacency constraints, use Graph Coloring, Chromatic Number and Map Constraints. For nearest-region geometry, use Voronoi Diagrams, Nearest Regions and Geometric Partitioning.
Return to the BTT Primary Mathematics Learning Hub.
Original enrichment guide with 24 original practice questions and separate worked answers. Rule 90 uses fixed-zero boundaries for finite-row exercises; Game-of-Life updates are synchronous.