Evolving cellular automata to solve global problems with local rules
Can a system of simple cells, each seeing only their immediate neighbors, collectively determine a global property of their configuration? This is the density classification problem — one of the classic challenges in emergent computation. Each cell must decide: are there more 1s or 0s across the entire lattice? But no cell can see the whole thing.
I used a genetic algorithm to evolve 1D cellular automata rules that solve this problem. The evolved rules discover strategies involving information transfer via particle-like signals — patterns that propagate through the lattice, collide, and resolve into the correct answer. Below, you can watch these strategies emerge and try them yourself.
Imagine 149 cells arranged in a ring, each either black (1) or white (0). At each time step, every cell simultaneously updates its state based on a fixed rule that considers only the cell itself and its 3 nearest neighbors on each side — a radius-3 neighborhood of 7 cells.
The task: after some number of steps, all cells should be black if the initial configuration had a majority of black cells, or all white if it had a majority of white cells.
This is deceptively hard. Each cell can only see 7 of the 149 cells. There's no central controller, no global memory, no message passing — just a lookup table mapping 7-bit neighborhoods to a single output bit. Yet somehow, the system must compute a global statistic (majority) from purely local interactions.
In fact, it's been proven that no CA rule can solve this problem perfectly for all inputs. But some rules get remarkably close.
A radius-3 binary CA rule is a lookup table with 27 = 128 entries. Each entry maps a 7-bit neighborhood pattern to a single output bit. The total number of possible rules is 2128 — roughly 3.4 × 1038. Far too many to search exhaustively.
The first known good solution was discovered by hand in 1978 by Gacs, Kurdyumov, and Levin. Their rule (GKL) uses an elegantly asymmetric strategy:
The insight is directional: 1s propagate information to the right, 0s propagate to the left. When these signals meet, whichever is in the majority wins. In my tests, GKL achieves ~85% accuracy on random initial configurations.
Can evolution find rules that humans couldn't? I set up a genetic algorithm:
Representation: Each individual is a 128-bit string — the complete CA rule table.
Fitness: Run the rule on 100 random initial configurations. Accuracy = fraction classified correctly.
Selection: Tournament selection (size 5) with elitism (top 2 survive unchanged).
Crossover: Mix of two-point and uniform crossover.
Mutation: Flip each bit with 3% probability.
Population: 100 individuals, evolved for 200 generations.
The population starts near zero — random 128-bit strings are almost certainly useless as classifiers. But within ~20 generations, the best individuals crack 60%, and by generation 100, the best evolved rule reaches ~77% accuracy.
Watch closely — the evolved rule creates expanding domains of uniform 0s and 1s, separated by boundaries that propagate as particle-like signals. Where a 0-domain meets a 1-domain, the boundary's movement depends on the local density. Eventually, the dominant value's domain swallows the rest.
This is the hallmark of good density classifiers: they develop an information-processing strategy based on particles (domain boundaries that move at characteristic velocities) and particle interactions (collisions that produce new particles or annihilate existing ones).
The hardest cases are near the threshold — initial configurations where roughly half the cells are 1 and half are 0. Any rule will struggle when the density is very close to 0.5.
Draw an initial configuration or generate a random one, then watch the cellular automaton evolve. Can you find cases where the evolved rule fails?
The density classification task is a microcosm of a deep question: how does collective computation arise from local interactions?
Biological systems solve similar problems constantly. Ant colonies decide where to forage without any ant seeing the whole territory. Neurons collectively represent concepts that no single neuron encodes. Immune cells coordinate responses to threats that no individual cell fully understands.
What's remarkable about the evolved CA rules is that they weren't designed — they were discovered by a blind search process. The particle-based information-processing strategy wasn't specified anywhere in the fitness function. It emerged because it works: it's an efficient way to aggregate distributed information using only local communication.
Mitchell, Crutchfield, and Das showed in 1996 that you can analyze these evolved rules using the framework of computational mechanics — identifying the "particles" (regular-expression-describable domain boundaries) and their interaction rules, effectively reverse-engineering the computation the CA performs. The evolved rules implement a form of distributed algorithm: information about local density propagates via particle velocities, and particle collisions perform the comparison.
No single cell "knows" the answer. The answer emerges from the dynamics of the whole system. That's emergent computation.