No local rule can count the votes

Put an odd number of cells in a ring, each holding $0$ or $1$, and ask them to hold a vote. At the end every cell should hold whichever value started in the majority. The difficulty is that no cell can see the ring. Each one updates, in lockstep with all the others, by looking only at its immediate neighbours — the same local rule everywhere, with no counter, no memory beyond its own state, and no cell in charge.

This is the density classification problem, posed by Norman Packard in 1988 as a test of what a cellular automaton can compute. It sounds easy, because a majority is the simplest global fact about a ring. It turns out that no single rule can do it — and that two rules can, which is the kind of answer that says the question was about something other than it looked.

Why a local rule cannot simply count #

A majority is a global fact in the strictest sense. Change a single cell in a ring that is one vote from a tie and the correct answer flips — so the final state of every cell must depend on every cell’s starting value, including the ones half the ring away. Information has to travel, and it can only travel as fast as the rule’s reach allows: with a rule that looks $r$ cells either side, influence spreads at most $r$ cells per step, so on a ring of $n$ cells the answer cannot be known anywhere until about $n/2r$ steps have passed.

That is a lower bound on time, and it is not the real obstacle. The real obstacle is that the cells must carry a count across that distance, and a cell holding one bit cannot hold a count. Whatever travels round the ring has to be encoded in patterns of 0s and 1s, and the rule has to make those patterns do arithmetic.

The rule in the first figure does something cleverer than counting. Each cell looks in one direction if it holds 0 and the other if it holds 1, so solid blocks of each value tend to grow, 0s spreading one way along the ring and 1s the other, and where two blocks meet a region of alternating cells forms and travels. The larger regions in the starting row tend to win, because they are more likely to be the ones that grow into solid blocks early. So the rule decides the vote not by counting but by a contest between regions, which is right whenever the majority shows up as larger regions — and most of the time it does.

The rule was not designed for voting. Gács, Kurdyumov and Levin published it in 1978 as an example in a study of fault-tolerant computation, where the point was a rule that could repair scattered errors in a uniform state; that it also classifies densities well was noticed later, and it became the benchmark every attempt at the problem is measured against.

Where the contest goes wrong #

Near a tie, the regions and the count part company.

With 76 ones and 73 zeros, the starting row is a near-tie, and what decides the contest is not the count but where the early solid blocks happen to form. In this ring the 0s formed a block that outgrew everything else, and the rule reached a uniform ring of 0s — a perfectly definite answer, and the wrong one. Nothing in the dynamics looks faulty. The rule did exactly what it always does; the starting row simply gave the minority the better position.

The pattern across many rings is the one the single example suggests. When the majority is large, it shows up as large regions, and the contest and the count agree. When the majority is a few cells, the contest is decided by arrangement rather than number, and the rule’s answer is close to a coin toss. Averaged over rings drawn with each cell fair, the rule is right about eight times in ten on rings of 149 cells, and that figure is dragged down almost entirely by the near-ties. Near-ties are not rare under that distribution: the margin of a fair random ring is a sum of fair coin flips, so it is typically about the square root of the ring’s length — the same scale on which a random walk wanders from home — and a margin of a dozen cells out of 149 is well within the region where regions and counts disagree.

No rule of the smallest kind does better than guessing #

The rule above looks three cells each way. A rule that looks only one cell each way — one of the 256 elementary rules — has much less to work with, and a complete census shows how little.

The census is sobering. No elementary rule does meaningfully better than a rule that ignores its input and answers 0. The rules at the top of the histogram have simply learned to say 0, which is right half the time because half the rings have a majority of 0s; the one extra ring they get right is the ring of all 1s, which is already uniform and which nothing disturbs. With a reach of one cell, no rule can move enough information round a ring to take a vote.

Larger reach helps, and never enough #

The natural hope is that a larger radius eventually solves the problem. It does not, at any radius, and the proof is short enough to state the idea of.

Mark Land and Richard Belew proved in 1995 that no two-state rule of any radius classifies every ring correctly. The argument turns on what a correct rule would have to do with long uniform blocks. A ring that is all 0 except for one long block of 1s must end as 0 if the block is less than half the ring and as 1 if it is more — so a correct rule would have to make the same block grow on one ring and shrink on another, while a cell deep inside the block, or deep in the background, sees exactly the same neighbourhood in both. The proof turns that tension into a contradiction by building configurations out of such blocks, and it uses nothing about the rule except that it is local and the same everywhere. The reach only changes how long the blocks have to be.

The impossibility is a statement about exactness. A rule of radius three can be right on the overwhelming majority of rings drawn at random, and evolutionary searches in the 1990s, followed by hand-tuned designs, pushed the success rate on random rings of 149 cells from the GKL rule’s eighty-two per cent to somewhere near eighty-nine. What no rule can do is be right on every ring, and the near-ties are where every rule’s errors concentrate, because they are the rings where a count and an arrangement disagree.

The local vote freezes #

The most natural local rule for a vote is the one that literally takes a vote: each cell becomes the majority of itself and its two neighbours. That is rule 232, and it fails in a way that makes the problem’s nature plain.

The local majority settles every disagreement between a cell and its neighbours and none between regions. It is also a rule that throws information away at every step — many different rows freeze to the same pattern — which is the irreversibility the first essay on these rules counted: a rule that merges states can never recover which of them it started from. Once each cell has a neighbour that agrees with it, it will never change, so the ring freezes into blocks of two or more, and the blocks of the minority are exactly as stable as those of the majority. A local vote produces local agreement, and local agreement is compatible with any global split. The problem was never that the cells could not agree; it was that they agreed too early, before the information needed to decide had arrived.

Two rules, one after the other #

Now the resolution, due to Henryk Fukś in 1997, and it uses the rule from the road where nobody overtakes.

Run rule 184 — the traffic rule — for about half the length of the ring. Then switch to rule 232, the local majority, for about half the length again. On a ring of $n$ cells, with $n$ odd, the exact schedule is $\lfloor (n - 2)/2 \rfloor$ steps of the first and $\lfloor (n - 1)/2 \rfloor$ of the second.

The two stages do two different jobs. Rule 184 conserves the number of 1s, so it cannot change the vote; what it does is rearrange the ring so that the vote becomes locally visible. After half a lap, if 1s are in the minority, every car has a gap ahead of it — no two 1s adjacent — while some 0s are adjacent; if 1s are in the majority, every gap has a car behind it — no two 0s adjacent — while some 1s are. The majority value is now exactly the value that appears doubled somewhere, and the minority value appears only in isolated cells — which is the pigeonhole principle at work, since a value with more cells than the other cannot keep every one of its cells apart.

That is the situation the local majority handles perfectly. Rule 232 erases isolated cells and preserves doubled ones, and a doubled cell next to an isolated cell of the other value spreads into it. Given a ring in which only the majority ever appears doubled, the local vote grows the majority’s doubled cells until they cover the ring. The rule that froze on a random ring finishes the job on a prepared one.

So the problem that no single rule can solve is solved by two rules in sequence, and the division of labour explains why one was not enough. A conserving rule can rearrange but never decide; a deciding rule can decide but only if the evidence is local. The first converts a global fact into a local one, the second acts on it, and a single homogeneous rule cannot switch between those two roles at the right moment, because nothing local knows when half a lap has passed.

Why a universal rule does not help #

There is an apparent paradox here that is worth settling, because an earlier essay has already shown that one elementary rule can compute anything. Rule 110 is universal: given the right starting row, it simulates any program, including a program that counts the 1s on a ring and reports the majority. Why, then, is there no single rule that votes?

Because universality is a statement about prepared inputs. A universal rule runs a program when the program and its data have been written into the starting row in a particular encoding, with room around them and a known place to read the answer; the density classification problem hands the rule a raw ring with no encoding, no room, and every cell required to end in the answer. The two questions sound alike and are not. Universality says what a rule can do when someone has laid out the problem for it; density classification asks what a rule can do with the problem as it arrives.

The two-rule solution sits exactly in the gap between them. Switching from rule 184 to rule 232 after half a lap is a small amount of preparation — an instruction, from outside, about when to change behaviour — and it is precisely the thing a single homogeneous rule cannot supply to itself. A cell cannot know how many steps have passed, because it has no clock; it cannot know the ring’s length, because it sees three cells. Give the cells a clock, or one extra bit of state that can carry a signal round the ring, and the problem dissolves. The impossibility is about what uniform, memoryless locality can do on raw data, which is a narrower thing than what computation can do.

An old difficulty in a new medium #

The failure of local rules to take a vote belongs to a family of results about aggregating many inputs into one decision, and the family resemblance is instructive.

Arrow’s theorem says no rule for combining rankings satisfies a short list of reasonable conditions. The discursive dilemma says a panel voting premise by premise can reach a conclusion the majority rejects. Both are impossibilities about aggregation under constraints that each seem harmless. The density classification theorem is one more: majority itself is perfectly well defined, and it is the constraint of computing it locally and uniformly that makes it unreachable. In each case the impossibility is escaped by giving something up — a condition, a procedure, or here, the insistence on a single rule — and in each case what has to be given up is the thing that looked most innocent.

What the pictures cannot show #

The impossibility proof. Land and Belew’s theorem covers every rule of every radius, and no figure here depicts the pair of configurations its proof constructs. The census of elementary rules and the failures of the GKL rule are evidence that the problem is hard; they are not the proof that it is impossible, which is an argument about all rules at once.

Correctness beyond fifteen cells. The two-rule schedule was checked exhaustively on every odd ring up to fifteen cells and on the rings drawn. Its correctness for every odd ring is Fukś’s theorem, proved by the argument about isolated and doubled cells above; the exhaustive check confirms the argument on 43,680 cases and cannot extend it.

The success rates. The GKL curve is measured on sixty rings per density, so each dot carries a sampling error of several per cent, and the dip near one half is real but its exact depth is not pinned down by this figure. The census of elementary rules, by contrast, is exact: every configuration was run.

Still open: how well one rule can do #

The exact problem is settled — impossible for one rule, possible for two. The approximate problem is not. For rules of a fixed radius, the best possible success rate on random rings of a given size is unknown; the best rules found by search and by hand reach close to eighty-nine per cent at 149 cells with radius three, and no one knows how far above that the optimum lies. There is evidence that the optimum declines as rings grow, since near-ties become more common in relative terms, but no proof of how fast.

Other relaxations have their own answers. Allowing each cell to act randomly changes the picture again: Fatès showed in 2013 that a stochastic rule can classify correctly with probability as close to one as desired, at the cost of time. Changing what counts as an answer — accepting a final checkerboard or a pattern of blocks instead of a uniform ring — lets rule 184 alone serve, which is how Capcarrere, Sipper and Tomassini framed it in 1996. Each relaxation moves the question from “can locality compute a majority” to “which weakening of the question is enough”, and the boundary between them is the interesting part.

The same tension, between aggregating preferences and doing so without a central counter, runs through the majority that goes in a circle, where a vote over three options can fail to have a winner at all. There the obstruction is in the preferences; here it is in the locality. In both, the familiar word “majority” hides a question that is harder than it looks.

A global answer, made local first #

A ring cannot take a vote by having each cell look at its neighbours, however far each cell can see. The best single rules come close by staging a contest between regions, and they fail exactly where the regions and the count disagree — at a near-tie. The most natural rule, the local majority, freezes before it can decide anything.

The solution is to split the work. A rule that conserves the count and moves the 1s like cars rearranges the ring until the majority is the only value that ever appears twice in a row; then the local majority, harmless now, finishes the vote. The first rule makes the answer visible and the second reads it off — and the two cannot be merged into one, because nothing on the ring knows when to stop the first and start the second.