A line that fires all at once

The problem was stated by John Myhill in 1957 and given its name by Edward Moore in print a few years later. A line of soldiers stands in a row, of any length. Every soldier has the same small brain, with a fixed number of possible states, and that number must not depend on the length of the line. All soldiers change state together at each tick of a common clock, and each new state depends only on the soldier’s own state and those of the two neighbours. At one end stands a general. All the others start asleep. At some moment later, every soldier must enter the state called firing, all at the same tick, and none may do so before.

The difficulty is that there is nothing to hold on to. A soldier cannot count to the length of the line, because the line can be longer than any number its brain can store. It has no way of knowing where it stands. Nothing tells it when a message has come from far off or near by. In the problem of counting votes, the corresponding kind of local rule was shown to be impossible. Here the outcome is the opposite. It seems at first as though no rule could work, and yet a solution can be written in a table of a modest size.

This essay builds one. The result has seventeen states, it was run on every length from 1 to 300 cells, and in every run all the cells fired at the same step.

The method: one signal three times as fast #

The solution uses one idea, usually credited to Marvin Minsky and John McCarthy: find the middle, and make it a second general. If that can be done, the two halves of the line are smaller versions of the same problem, and they run at the same time. If all the halves reach the same length at the same moment, the recursion ends with every cell a general at the same step, and then everyone can fire.

Finding the middle without counting is a nice trick. The general sends two signals down the line. A fast signal moves one cell per step, reaches the far end, bounces and comes back. A slow signal moves one cell every three steps. When the fast one returns, how far has the slow one come? If the line has length $L$ and they meet at distance $x$ from the general, the fast signal has travelled out and part of the way back, $2L - x$, in the time the slow one has travelled $x$. So $2L - x = 3x$, and $x = L/2$. They meet at the middle, whatever $L$ is, and no cell had to know $L$. That is a calculation in units of distance and speed, and the soldiers perform it by passing a marker on or holding it for a tick. The automata met in eight rules and a triangle produce their patterns by accident of a rule, whereas this rule is designed so that its pattern is a piece of arithmetic.

The third is not arbitrary. A slow signal of speed $1/m$ meets the returning fast one at $2L/(m + 1)$, so a speed of one third gives a half, a speed of one seventh gives a quarter, and a speed of one fifteenth gives an eighth. Any fraction with a suitable denominator can be cut off in this way, and that is what the fastest rules exploit, as the discussion further on explains. A small slow-down of the signal, one extra tick of waiting in each cell, moves the meeting point by a definite amount, and the number of ticks a signal waits is exactly the kind of thing that a cell with a few states can hold.

At that point the meeting cell becomes a new general. If the line has an odd number of cells between the walls, the meeting occurs in one cell. If it is even, the middle falls between two cells, and they recognise each other: one holds a slow signal in its last phase of waiting, its neighbour holds the returning fast signal, and both become generals. Either way, the two halves have exactly the same number of empty cells, and they begin together. Each new general then sends signals both ways. The old general stays inert, serving as a wall.

The recursion is visible in the diagram as triangles within triangles. Each general launches a pair of signals into the stretches on either side of it. Their paths are the lines with slopes one and three in the picture, and each pair ends at a new general at the middle of its stretch. By the bottom of the diagram every cell is a general. A cell with a general or the end of the line on both sides then knows that there is nothing left to split, and the rule is that it fires.

A rule table and nothing else #

It is easy to get this slightly wrong and describe an algorithm that uses more than its neighbours. So the version here is written as a genuine automaton: the next state of each cell is read from a table keyed by the states of three adjacent cells, and the table is applied at every cell at every step. A state is a small set of flags, one for general, one for newly made general, one for fired, one for a fast signal in each direction, and one for a slow signal in each direction with a phase of 0, 1 or 2 that counts its three-step gait.

Filling the table as lines are run shows that a finite number of states suffices for every length. Short lines use only a few: 6 states by length 2, 14 by length 5, and 17 by length 10. No new state has appeared in any line up to 300. New entries in the table do continue to appear slowly as the arrangements of neighbours get used, 142 by length 100 and 155 by length 300, but the count of possibilities is bounded by the cube of the number of states, and in practice it stays small.

Nothing in the argument so far proves simultaneity at every length, but it is not hard to prove. At each level all the stretches between walls have the same number of empty cells, since an odd number $k$ becomes $(k - 1)/2$ on both sides and an even $k$ becomes $k/2 - 1$ on both sides. The time for a stretch to split depends only on $k$. So every split at a level happens at the same step, and the bottom of the recursion is reached in every stretch at once. In the run on every length from 1 to 300 there is an explicit test: at the first step where any cell fires, all must fire, and none did so earlier. It never failed.

The smallest lines by hand #

Following a very short line shows how much bookkeeping the table hides. With four cells and the general at the left, the fast signal reaches the last cell at step 3, turns round there at step 4, and meets the slow signal in the third cell at step 5. That cell becomes a general at step 6, and its two neighbours on the right and left each form a stretch of one empty cell. The new general launches a fast and a slow signal into each, those signals bounce at once, and two steps later each of those cells has become a general too. Every cell is now a general, each with a general or an edge on both sides, and at the following step all four fire. So the line of four takes ten steps, where the floor is six.

The lengths around it behave the same way, with small differences. A line of two takes a few steps, a line of three a few more, and the increments are irregular, because an odd stretch has one middle cell and an even stretch has two, and these take one step more or less to resolve. All of that is decided by the parity of each stretch as the recursion proceeds, and so the small variations in the firing time are a record of the binary digits of the length of the line. As with the column of bits in Rule 30, the exact sequence can be read from the rule and has no simpler description, though here each bit has an obvious meaning.

How long it takes #

Time for a stretch of length $L$ is about $\tfrac32 L$ for the signals to meet, and then the halves take about $\tfrac32 \cdot \tfrac L2$, and so on. This is the geometric series that governs any halving process, and it adds up to $3L$.

The measured times fall just below $3n$: 26 at ten cells, 294 at a hundred, 594 at two hundred, 892 at three hundred. The recursion shows up as slightly different steps depending on how the length breaks down in halves. At $n = 128$ the time is 382, which is two less than three times the length: a power of two has rather simple halvings.

The last figure of this kind makes the arithmetic visible. In a line of 96 cells, new generals appear in rounds at steps 144, 216, 252, 270, 279 and 283, so the gaps are 144, 72, 36, 18, 9 and 4, and the firing is at step 284. The first round makes one general, the second two, then four, then eight, then sixteen, and then 64 as the last round fills in the remaining cells. So the whole time is spent on a series of halvings, and half of it on the first split alone. It is the opposite of a parallel speed-up. The first round must wait for a signal to go the whole length and back, and nothing can happen in the right half until the first general has created the second.

The floor: twice the length #

Can it be faster? A simple argument gives a limit. Information moves at most one cell per step, as each state depends only on immediate neighbours. So at step $n - 1$ the far cell is first able to feel anything at all. A signal from it takes another $n - 1$ steps to return. The general cannot distinguish a line of this length from a longer one before step $2n - 2$. A rule that fired earlier than that on a line of length $n$ would fire at the same time on a longer line, leaving the far end of the longer line unfired. So $2n - 2$ is a floor.

The surprise is that the floor can be attained. Eiichi Goto gave a solution in 1962 with a very large number of states, thousands of them, and this was never published in full. Abraham Waksman reduced it to 16 in 1966. Robert Balzer used a program to search and reached 8 in 1967. Jacques Mazoyer got to 6 in 1987, with a solution that he argued for by hand and verified by computer.

The minimal-time approach still halves, but it is smarter about when the halving begins. If a line has length $n$, then waiting until $3n/2$ for the first middle general uses most of the $2n$ available. So the general sends many signals at once, of speeds $1, 1/3, 1/7, 1/15, \dots$, with speeds $1/(2^k - 1)$. As a reflected signal comes back, it meets the speed-$1/(2^k - 1)$ signal at the point $n/2^{k-1}$ from the general. So the cuts at a half, a quarter, an eighth and so on are all prepared in advance and come into existence in the right order. Each stretch then begins its own work at precisely the time it needs to, with no waiting. The fact that infinitely many speeds are needed in general does not break the finite-state condition, because the states are organised so that each new speed is built by a local rule from the previous one. That is the real creativity in Waksman’s and Balzer’s solutions.

Numbers of states are pushed down partly by computer search, but a state can also be merged only by proving the whole line still works, and that is hard. Balzer showed that no minimal-time solution exists with four states, and Hiroshi Umeo and others have written down many six-state solutions since, but no one knows about five. In all cases, the rule has to depend on the geometry in a subtle way, and the search space for a table with five states is large enough to be out of reach by simple means. Peter Sanders found an error in Balzer’s exclusion of four states in 1994, and repaired it with a better search, which shows how delicate this is.

Relatives #

It is natural to compare this with the clocks that fall into step. Kuramoto’s oscillators synchronise spontaneously, through coupling, with an unbounded number of states, and they do so only approximately. A firing squad synchronises exactly, in a fixed number of states and on a command, and it is deterministic. It also finishes, while a ring of oscillators can settle into a twist instead of agreeing. In a chain of coupled clocks, length alone can destroy synchrony. And a line of cars obeying a local rule carries signals at fixed speeds in the same way, with jams moving backwards at a speed set by the rule, but there nothing has been arranged for them to meet. Here the difference is that signals carry information deliberately, and they go at exact speeds that the rule fixes. Nothing about this rule would survive a small random error: a single flipped state in the line would cause a stretch to mis-split and the whole firing would fail. This has been studied too, and fault-tolerant versions exist at a cost.

The problem has also been varied extensively. A general in the middle of the line can fire the line in $n - 2 + \max(k, n - k + 1)$ steps. In a ring, or in a two-dimensional rectangle, or on a general graph, the minimal time is typically a function of a distance to the farthest cell and back, as the light cone suggests. Hiroshi Umeo and his collaborators have built optimal two-dimensional solutions with few more states.

There is a practical use, and the problem began with one. Synchronising the parts of a circuit without a global signal was a real concern to those who built the first parallel computers, and early computer architects had to think about how a command could reach every unit in a way that they could all act on simultaneously. Modern chips still face a version of it, in which a clock has to be distributed across a wide area with very small relative skew, though the local-rule form is only one of many models considered. The rule that computes showed that a one-dimensional automaton can be a universal computer. Here the same kind of table is built to do one precise act, with no computation needed beyond its own timing.

What these runs establish #

The rule built here was tested exhaustively at each length up to 300 with a direct check that no cell fires early and that all fire together. The argument above gives a proof for all lengths, relying on the recursion on empty cells; the runs test the implementation of that argument rather than the argument. Cell-state counts are those actually reached in the runs and could in principle be increased by an initial condition never used, such as a general not at the end, which this rule was not designed for. The firing time $3n$ is an approximation, with exact values in the figure.

None of the published minimal-time solutions were reconstructed here. All statements about Goto, Waksman, Balzer, Mazoyer and Sanders come from the literature, as do the state counts, which depend on what is counted as a state and on how the general itself is treated. The speed-signal description of minimal-time solutions is a sketch. Real rules contain many more details about how to carry the signals in a bounded number of states, and those are what the search and the human ingenuity went into.

Still open: five states #

Does a five-state solution exist? The problem has had this exact form since at least the 1980s. Six states work and four do not. Between them is one number, and there is no structural argument either way. A brute-force enumeration of all five-state tables is not out of the question in terms of the number of tables, but the constraint is that the rule must work for every length, and proving this for a given table requires an invariant that nobody has found how to search for automatically. So far, searches have ruled out large classes with certain symmetries and restricted forms. Non-minimal-time solutions with fewer states are known: the question of how few states suffice if the time is allowed to be larger has an answer. Umeo and his colleagues have found four-state solutions for particular lengths and particular arrangements, but a four-state solution for all lengths with no time constraint has not been settled either.

Telling the time by meeting #

A fast signal that bounces and a signal of a third of its speed meet exactly at the middle of any stretch. That one piece of arithmetic is all that a cell needs in order to halve a line whose length it does not know. Halving until nothing is left, with all stretches kept equal, gives a table of seventeen states that fires every line up to 300 at a single step, in just under three times the length of the line. Sending a whole family of signals with speeds $1/(2^k - 1)$ brings the time down to the floor of twice the length, and with enough cleverness to six states.

The problem looks as though it needs a global clock or a counter, and all it needed was two speeds. What looks like a coordination problem turns out to be a geometry problem drawn in the spacetime of the line, where every cut is the crossing of two straight lines.