Cellular automata are mathematical models made from many simple cells that update over time using local rules. They help students see how complex patterns can grow from simple instructions. This cheat sheet summarizes the main ideas, classic rules, and modeling uses of cellular automata.
It is useful for applied math, computer science, biology, physics, and systems modeling.
Key Facts
- A cellular automaton has a grid of cells, a set of possible states, a neighborhood rule, and an update rule applied at each time step.
- In a 1D elementary cellular automaton, each cell has state 0 or 1 and updates from the pattern made by its left neighbor, itself, and its right neighbor.
- A 3-cell binary neighborhood has 2^3 = 8 possible input patterns, so an elementary rule is described by 8 output bits.
- There are 2^8 = 256 elementary cellular automaton rules because each of the 8 neighborhood patterns can output either 0 or 1.
- For an elementary rule, the next state can be written as s_i(t + 1) = f(s_{i - 1}(t), s_i(t), s_{i + 1}(t)).
- In Conway’s Game of Life, a live cell survives with 2 or 3 live neighbors, a dead cell becomes live with exactly 3 live neighbors, and all other cells are dead in the next step.
- Boundary conditions describe what happens at the edge of the grid, such as fixed edges, empty edges, or wraparound edges.
- Cellular automata are deterministic when the same starting pattern always produces the same future pattern under the same rule.
Vocabulary
- Cell
- A cell is one location in the grid that holds a state at a specific time.
- State
- A state is the value or condition of a cell, such as 0 or 1, dead or alive, or empty or occupied.
- Neighborhood
- A neighborhood is the set of nearby cells used to decide how a cell updates.
- Update Rule
- An update rule is the function that determines a cell’s next state from its current neighborhood.
- Time Step
- A time step is one round of updating every cell according to the rule.
- Boundary Condition
- A boundary condition states how cells at the edge of the grid are treated during updates.
Common Mistakes to Avoid
- Updating cells one at a time and using the new values immediately is wrong for standard cellular automata because all cells should update simultaneously from the previous time step.
- Forgetting boundary conditions is wrong because edge cells have missing neighbors unless the model defines how the edge behaves.
- Confusing a rule number with a cell state is wrong because the rule number names the entire update table, while a state is the value of one cell.
- Assuming simple rules always make simple patterns is wrong because cellular automata can produce complex, repeating, random-looking, or stable behavior from short rules.
- Treating a model pattern as a perfect real-world prediction is wrong because cellular automata depend on simplified assumptions about space, time, and local interactions.
Practice Questions
- 1 In a 1D elementary cellular automaton, how many possible 3-cell binary neighborhoods are there?
- 2 How many elementary cellular automaton rules are possible if each of the 8 neighborhoods can output 0 or 1?
- 3 In Conway’s Game of Life, a dead cell has exactly 3 live neighbors. What is its state in the next time step?
- 4 Explain why a cellular automaton can be useful for modeling a forest fire, even if it does not include every detail of a real forest.
Understanding Cellular Automata
The most important technical detail is that cells are normally updated simultaneously. Every cell reads the old grid, calculates a next state, then the complete new grid replaces the old one. If a program changes cells one at a time, later cells may read values that have already changed.
That produces a different model, even when the written rule is identical. A reliable programming method uses two grids. One stores the current generation.
The other stores the next generation. This is why careful hand calculations need a clear row by row procedure.
Elementary rule numbers are compact labels for lookup tables. Start by listing the eight possible three-cell patterns in a fixed order, often from all ones down to all zeros. Write one output for each pattern in that same order.
Reading the output sequence as a binary number gives the rule number. Rule 30, for example, has the output sequence zero zero zero one one one one zero in the usual ordering.
Changing the ordering changes the displayed rule number. Students should state the pattern order before comparing calculations, diagrams, or computer code.
Some rules quickly become blank or repeat a simple pattern. Others make long, irregular looking structures. This difference is important because irregular behavior does not necessarily mean randomness.
A fully deterministic rule can produce a pattern that is difficult to predict far into the future. In the Game of Life, small starting arrangements can become stable objects, repeating oscillators, or moving gliders. A glider appears to travel across the grid, although no single cell moves from one location to another.
Its changing shape recreates itself one step away. Collisions between such patterns can create, remove, or redirect structures.
When a cellular automaton is used as a model, its assumptions matter as much as its output. A traffic model may treat each road section as one cell and each car as present or absent. A wildfire model may use cells for patches of land with states such as unburned, burning, or burned.
These choices leave out details such as different vehicle speeds, wind gusts, moisture, and human decisions. Cell size and time step affect the result too. Large cells can hide local variation.
Short time steps can show faster changes. Real systems often need probabilities because identical conditions do not always lead to identical outcomes. Students should examine the rule, the boundary choice, and the starting pattern before deciding what a simulation means.