CA as a Computer research thread

Instead of hand-wiring logic like Wireworld, search rule space for rules that compute. The benchmark is the classic density classification task: a 1-D rule (radius 3, 128-entry table) must decide whether the initial row had more 1s than 0s, using only local updates — no cell can see the whole line. A genetic algorithm breeds rules; you watch fitness climb and the champion classify live.

—
0-cell   1-cell  — space runs top→bottom. The strip above the line shows the true majority colour; a correct rule fills the whole sheet with it.

Run

generation 0
champion —
pop mean —
best ever —

GKL (the famous hand-designed rule) scores ≈0.81. The GA usually finds "block-expanding" strategies in the 0.6–0.8 range. No rule is known to beat ≈0.82 — that ceiling is the open problem.

Evolution knobs

Each generation, every rule is re-tested on a fresh random batch of initial conditions, so fitness can't overfit one set. Elites survive; the rest are crossover + mutation of the top half.

The task

ρ-classification: given a random binary row of length 149, the rule must converge to all-1s if the row started >50% ones, else all-0s. The catch: each cell only sees ±3 neighbours, so the line has to compute global density from local interactions — a toy model of distributed computation.

🖥️ Research thread — open problems

Hand-building gadgets (Wireworld adders, Rule 110) proves CAs can compute. The deeper question is whether computation can be discovered automatically, and how local rules give rise to global information processing. Open directions:

  1. The density ceiling. Land & Belew proved no two-state rule classifies density perfectly; the best known sit near 0.82. How close to that bound can search get, and what particle/glider strategies do the winners use? (Crutchfield–Mitchell "computational mechanics" reads the answer off the space-time diagram.)
  2. Particles as signals. Evolved classifiers work by emitting gliders whose collisions carry information. Automatically extracting this "particle calculus" from raw runs is a live analysis problem — and a bridge to interpretability.
  3. Beyond one task. Synchronisation, parity, and arbitrary boolean functions are all targets. Searching rule space for universal computation — rather than hand-building it — is largely open above 1D.
  4. Better search. GAs are the classic tool, but coevolution (evolving hard test cases alongside rules), novelty search, and gradient relaxations of the rule table are under-explored and could break the 0.82 plateau or prove it's a true wall.
  5. Reservoir view. The same substrate that classifies density can act as a reservoir computer: freeze the rule, read out a linear layer. Mapping which rules make good reservoirs ties this thread to modern ML.