Shiffman, Chapter 7

Cellular Automata

Wolfram's elementary CA, Conway's Game of Life, and the stunning complexity that emerges from the simplest possible rules.

Prerequisites: None specific. Fresh start — we leave motion behind and work with grids of cells.

Chapters

Simulations

Quizzes

Chapter 0: What Is a CA?

In this chapter, we take a major turn. No more vectors, no more forces. Instead, we build a system out of the simplest digital element possible: a single bit. A cell with a state of 0 or 1.

A cellular automaton (CA) is a model of "cell" objects with these characteristics:

Component	Description
Grid	Cells live on a grid (1D, 2D, or higher).
States	Each cell has a finite set of states (simplest: 0 or 1).
Neighborhood	Each cell has a defined set of neighbors.
Rules	A cell's next state is a function of its current neighborhood.

Why CA matter: They are complex systems. Simple elements, operating in parallel, with local rules, producing emergent behavior. Ulam studied crystal growth. Von Neumann imagined self-replicating robots. Wolfram argued CA are relevant to biology, chemistry, and physics. All from grids of 0s and 1s.

What are the four components of a cellular automaton?

Grid, states, neighborhood, and rules Particles, forces, velocity, and acceleration Cells, colors, pixels, and frames

Chapter 1: Elementary CA

Stephen Wolfram asked: "What is the simplest cellular automaton we can imagine?" The answer is surprisingly powerful.

The simplest CA has: (1) a 1D grid — a line of cells; (2) two states — 0 or 1; (3) a neighborhood of three — the cell itself plus its left and right neighbors.

How many neighborhood configurations? Three cells, each 0 or 1, means 2³ = 8 possible neighborhoods. For each configuration, we define the next state (0 or 1). That means a complete ruleset is 8 bits — and there are 2⁸ = 256 possible rulesets.

The standard approach: start generation 0 with all cells at state 0 except the middle cell at state 1. Apply the ruleset to compute generation 1, then generation 2, and so on. Stack the generations vertically, coloring 1 as dark and 0 as light.

How many possible rulesets exist for a Wolfram elementary CA?

8 256 (because a ruleset is 8 bits, and 2^8 = 256) 512

Chapter 2: Rulesets

A ruleset maps each 3-bit neighborhood to an output state. Since the neighborhood is a 3-bit binary number, we can index it directly. The ruleset for "Rule 90":

Neighborhood	111	110	101	100	011	010	001	000
Output	0	1	0	1	1	0	1	0

The binary sequence 01011010 is decimal 90 — hence "Rule 90." It produces the Sierpinski triangle.

The double-buffer trick: You cannot overwrite cell states while computing the next generation. Cell 6's new state depends on cell 5's old state. Solution: use two arrays. Compute all new states into a fresh array, then swap.

pseudocode
next = new array(cells.length)
for i in 1..cells.length-2:
  left   = cells[i-1]
  middle = cells[i]
  right  = cells[i+1]
  next[i] = ruleset[toBinary(left, middle, right)]
cells = next

Why do we need two arrays when computing the next generation?

Because overwriting a cell's state before its neighbors are processed would corrupt those neighbors' calculations Because one array stores colors Because arrays can only be read once

Chapter 3: Wolfram Classes

Of 256 rulesets, most produce boring results. Wolfram classified the outcomes into four categories:

Class	Behavior	Example
1: Uniformity	All cells become the same state	Rule 222
2: Repetition	Cells oscillate in a regular pattern	Rule 190
3: Random	Appears chaotic, no discernible pattern	Rule 30 (used in Mathematica's RNG!)
4: Complexity	Mix of repetition and randomness — the sweet spot	Rule 110

Class 4 is the jackpot. Rule 110 is proven to be Turing complete — meaning this trivially simple system of 0s and 1s can, in principle, compute anything a modern computer can. Complexity from the absolute minimum of ingredients.

Which Wolfram class exhibits the properties of a complex system?

Class 2 (repetition) Class 3 (random) Class 4 (complexity) — a mix of pattern and unpredictability

Chapter 4: The Game of Life

In 1970, mathematician John Conway invented the Game of Life. It's a 2D cellular automaton with remarkably lifelike behavior.

The setup: a 2D grid of cells. Each cell is alive (1) or dead (0). Each cell has eight neighbors (the 3×3 block surrounding it, minus itself).

Conway's goals: No pattern should grow without limit (proven). Some patterns should appear to grow without limit. Simple patterns should grow, change, and eventually stabilize, oscillate, or die. In Wolfram's terms: Class 4 behavior.

How many neighbors does each cell have in the Game of Life?

4 (up, down, left, right) 8 (the 3x3 block surrounding it, minus itself) 2 (left and right)

Chapter 5: Life Rules

Instead of defining an outcome for all 512 possible 9-cell configurations, Conway defined rules based on the count of live neighbors:

Death: Overpopulation

A live cell with 4+ live neighbors dies.

↓

Death: Loneliness

A live cell with 0-1 live neighbors dies.

↓

Birth

A dead cell with exactly 3 live neighbors becomes alive.

↓

Stasis

All other cells stay as they are. (Alive with 2-3 neighbors stays alive. Dead with ≠3 stays dead.)

These four rules produce an astonishing variety of patterns: static "still lifes," oscillating "blinkers," and moving "gliders" that travel across the grid.

Under what condition does a dead cell come to life?

It has exactly 3 live neighbors It has 2 or more live neighbors It is adjacent to any live cell

Chapter 6: Programming Life

The implementation mirrors the 1D CA, but with a 2D array and a nested neighbor-counting loop:

pseudocode
next = new grid[cols][rows]
for x in 1..cols-2:
  for y in 1..rows-2:
    neighbors = 0
    for i in -1..1:
      for j in -1..1:
        neighbors += board[x+i][y+j]
    neighbors -= board[x][y]  # Don't count self!

    if board[x][y] == 1 and neighbors < 2:  next[x][y] = 0
    elif board[x][y] == 1 and neighbors > 3: next[x][y] = 0
    elif board[x][y] == 0 and neighbors == 3: next[x][y] = 1
    else: next[x][y] = board[x][y]
board = next

The same double-buffer trick: Just like the 1D CA, we compute all new states into a separate grid, then swap. Without this, the order we process cells would corrupt the computation.

When counting neighbors, why do we subtract the cell's own state?

Because the nested loop includes the cell itself in the 3x3 block, and we only want the 8 surrounding cells To normalize the count To handle edge cells

Chapter 7: Variations

The Game of Life is just the beginning. Here are ways to push CA further:

Variation	Idea
Hexagonal grids	Each cell has 6 neighbors instead of 8. Different dynamics.
Probabilistic rules	"80% chance of dying" instead of guaranteed death. Stochastic CA.
Continuous states	State is a float (0.0 to 1.0) instead of a binary. Smooth gradients.
Image processing	Pixel = cell, color = state. Blurring, ripples, ink dispersion.
Moving cells	Cells aren't fixed — combine CA with flocking or particle systems.
Historical	Cells remember past states. Adaptive behavior over time.

OOP cells: By making each cell an object (with state, previous state, location, color history), you open up richer visualizations. Color a cell blue when it's born, red when it dies, and you can see the wave of life flowing through the grid.

What is a "continuous" variation of a cellular automaton?

One where cell states are floating-point numbers instead of binary 0/1 One that runs continuously without stopping One where the grid grows over time

Chapter 8: Game of Life Simulation

Below is a live Game of Life. Click/tap cells to toggle them. Press Play to run the simulation, or Step to advance one generation at a time.

Conway's Game of Life

Click/tap to toggle cells. Watch still lifes, blinkers, and gliders emerge from random initial conditions.

Gen: 0

Things to look for: "Blinkers" (3 cells in a row that oscillate), "blocks" (2x2 squares that never change), and "gliders" (5-cell patterns that travel diagonally). These emerge spontaneously from random initial states.

What is a "glider" in the Game of Life?

A pattern that appears to move across the grid as cells turn on and off A cell that never dies A group of cells that blinks

Chapter 9: Summary

Topic	Key Takeaway
CA basics	Grid + states + neighborhood + rules
Elementary CA	1D, 2 states, 3-cell neighborhood, 256 rulesets
Wolfram classes	Uniformity, repetition, randomness, complexity
Double buffer	Never overwrite cells while computing — use two arrays
Game of Life	2D, 8 neighbors, 4 simple rules → lifelike behavior
Birth rule	Dead cell + exactly 3 neighbors = alive
Death rules	Too few (<2) or too many (>3) neighbors = death

The lesson: Cellular automata are perhaps the purest demonstration that complexity can emerge from simplicity. A grid of bits following the most basic rules can produce patterns that mirror nature — from textile cone snail shells to the growth of crystals.

What we covered:

• Wolfram's elementary CA
• 256 rulesets, 4 classes
• Conway's Game of Life
• Birth, death, stasis rules
• Double-buffer technique
• OOP cells and variations

What comes next:

Chapter 8: Fractals. Recursion, self-similarity, the Koch curve, fractal trees, and L-systems. Nature's geometry, built from a function that calls itself.

What programming technique prevents corruption when computing the next CA generation?

Processing cells from right to left Using a double buffer (writing to a separate array, then swapping) Using floating-point states