Matpic
mathematics, in pictures
Concept

Locality

The restriction that each part of a system is affected only by what is immediately next to it. It is what makes a cellular automaton's global behaviour surprising, since every rule in it sees only its immediate surroundings.

Named by 3 essays across 2 fields — each of them below, with the objects they name alongside it.

Elementary cellular automaton, rule 90. A row of cells evolving downward, each cell decided by the three above 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.

dynamics · Cellular automata Elementary cellular automaton, rule 110. A row of cells evolving downward, each cell decided by the three above it.

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.

dynamics · Cellular automata What a sentence of depth 2 can reach. Two rings of points, of 14 and 19 points, each with a run of 9 consecutive points marked as the neighbourhood a sentence of depth 2 can inspect.

The distance a sentence can see

A first-order sentence with three quantifiers cannot notice anything about a graph beyond a fixed distance from the points it names. That single limitation is why it cannot say connected, and why the failure survives every attempt to add more quantifiers.

logic · Ehrenfeucht–Fraïssé games

Named alongside it

The objects these essays reach for when they reach for this one.

Cellular automatonIterationBinaryComputationConnectivityDeterminismElementary equivalenceExhaustive searchExpressive powerGliderHalting problemNeighbourhood

All concepts