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.