Concept
Cellular automaton
A row or grid of cells updated together, each one deciding its next state from its immediate neighbours. The rule is a lookup table on the neighbourhood, and the interest is in how much behaviour a very small table can produce.
Named by 2 essays across one field — each of them below, with the objects they name alongside it.
Eight rules and a triangle
A row of cells, each one deciding its next state from the three above it. Eight cases, one bit of output each — a rule that fits in a byte, and 256 of them in total. One of those bytes draws Pascal's triangle.
The rule that computes
One of the 256 elementary rules can run any program. Not simulate one, not approximate one — a machine that can compute anything computable, built from a lookup table with eight rows and nothing else.
Named alongside it
The objects these essays reach for when they reach for this one.
IterationLocalityBinaryComputationDeterminismGliderHalting problemPascals triangleRule 110Rule 90Self-similarityState space