Cellular Automata

Elementary cellular automata (ECAs) are the simplest class of systems that exhibit emergence: local, deterministic rules give rise to globally complex patterns.

Setup

A 1D ECA consists of a row of cells, each either 0 or 1. At each time step, every cell's new state is determined by looking at a neighbourhood of three cells: the cell itself and its two immediate neighbours.

With three binary cells, there are $2^3 = 8$ possible neighbourhood patterns. Mapping each pattern to a 0 or 1 output requires $2^8 = 256$ bits — so there are exactly 256 distinct rules, numbered 0–255 (Wolfram's numbering scheme).

Rule Encoding

For a neighbourhood $(l, c, r)$ — left, centre, right — the index into the rule is:

$\text{index} = 4l + 2c + r$

and the output bit is:

$\text{output} = \left(\text{rule\_number} \gg \text{index}\right) \mathbin{\&} 1$

For example, Rule 110 in binary is 01101110:

Notable Rules

• Rule 110: Turing complete — capable of universal computation.
• Rule 30: Chaotic — used by Mathematica's Random[] function for years.
• Rule 90: Produces the Sierpiński triangle fractal.

Boundary Conditions

We use periodic boundary conditions: the leftmost and rightmost cells are treated as neighbours of each other. This avoids edge effects.

Your Task

Implement three functions:

• rule_lookup(rule_number) — return a dict mapping each (l, c, r) tuple to its output bit
• apply_rule(state, rule_number) — apply one step of the CA, returning the new state list (same length, periodic BC)
• run_ca(initial_state, rule_number, n_steps) — return a list of n_steps + 1 states (including the initial state)