In The Feynman Lectures on Computation, Richard Feynman poses a neat puzzle about synchronizing finite state machines that act as a general and a line of soldiers. He could solve it, but not in the minimum possible time, and he closed his description with a Fermat-like remark: someone had found a minimum-time solution, it was very difficult, and the reader should not be so ambitious.
The original version of this post quoted another writer's introduction and a long passage from the book. It has been replaced with a summary in our own words, an explanation of how the puzzle is solved, and the history of the minimum-time answer.
The puzzle in plain words
Feynman sets it as Problem 3.4, just before he introduces Turing machines. Picture a long line of N identical finite state machines, the "soldiers", with a "general" at one end. Time moves in discrete steps. The rules are:
- At each step, every machine's next state depends only on its own state and the states of its two immediate neighbors.
- All soldiers start in the same quiet state. The general starts things off with a single "fire" signal to the soldier next to him and then does nothing more.
- The method must work for any N. Since each soldier is a finite state machine with a fixed number of states, no soldier can count the line or be given a number.
- The goal is for all soldiers to enter a special "fire" state at the same step, for the first time, in the shortest possible time.
The difficulty is that no soldier knows how long the line is, and each one can only talk to its neighbors. Yet they must all agree on the same instant.
Why it matters to digital designers
This is the classic firing squad synchronization problem, first proposed by John Myhill in 1957 (Wikipedia: firing squad synchronization problem). It is a pure form of a real design question: how do many identical local cells, each seeing only its neighbors, reach a global agreement? The same idea appears in systolic arrays, cellular automata, distributed reset and start-up in large arrays of processing elements, and in network protocols where nodes have only local knowledge.
The key idea: find the middle
The usual solution splits the line in half, again and again. The general sends two signals down the line at once: a fast one that moves one soldier per step, and a slow one that moves one soldier every three steps. The fast signal reaches the far end, bounces back and meets the slow signal exactly in the middle. The soldier (or pair) there becomes a new general for each half, and the process repeats in both halves at once. When every segment is a single soldier, all of them fire together.
Deep dive: the numbers and details
This part holds the timing of the halving solution, the minimum-time bound and the history of the state counts. Skip it if the overview is all you need.
Why the signals meet in the middle
Let the line have length n. The fast signal (speed 1) travels to the end and back, so after time t (for t > n) it is at position 2n - t. The slow signal (speed 1/3) is at position t/3. They meet when 2n - t = t/3, that is t = 3n/2, at position n/2. The midpoint is found without anyone counting.
Total time of the halving solution
Each level costs about 3/2 times the length of the current segment, and the segments halve each time:
T(n) = 3n/2 + T(n/2) = 3n/2 + 3n/4 + 3n/8 + ... ≈ 3n
This is the McCarthy and Minsky style solution, which takes about 3n steps. For a line of 100 soldiers it fires at around step 300.
The minimum possible time: 2n - 2
No solution can be faster than 2n - 2 steps. The signal from the general needs n - 1 steps to reach the last soldier, and the last soldier cannot know it is last until it has seen that it has no neighbor. Information about the far end then needs another n - 1 steps to get back to the soldier next to the general, who cannot fire until it knows the length of the line. So the total is at least (n - 1) + (n - 1) = 2n - 2.
| Soldiers n | Halving solution (about 3n) | Minimum time (2n - 2) |
|---|---|---|
| 10 | about 30 | 18 |
| 100 | about 300 | 198 |
| 1,000 | about 3,000 | 1,998 |
The minimum-time solutions reach this bound by sending many signals at different speeds (1, 1/3, 1/7 and so on) so the line is divided into halves, quarters and eighths in parallel rather than one level after another.
History of minimum-time solutions
| Year | Who | States per soldier |
|---|---|---|
| 1957 | John Myhill poses the problem | - |
| 1962 | Eiichi Goto, first minimum-time solution | Thousands |
| 1966 | Waksman | 16 |
| 1967 | Balzer, who also argued no 4-state solution exists | 8 |
| 1987 | Mazoyer, best known solution | 6 |
Source: Firing squad synchronization problem: solutions. Balzer's search for 4-state solutions was later found to be incomplete, but a corrected search confirmed that none exists. Whether a 5-state solution exists is still an open question.
Thinking about it as a hardware designer
- State encoding: a 6-state soldier needs 3 flip-flops; Goto's thousands of states would need over 10. The race to fewer states is a race to smaller cells.
- Local rules only: each cell's next-state logic has three inputs (left, self, right), so it is a pure lookup table. With 6 states that is 6 x 6 x 6 = 216 entries, plus boundary cases.
- Simulation exercise: coding the halving solution in Verilog or VHDL as an array of identical cells is a good way to practice parameterized, generate-based design and to check that every cell fires on the same clock.
Further reading
- Firing squad synchronization problem (Wikipedia)
- Feynman Lectures on Computation, anniversary edition, edited by Tony Hey (Routledge)


Your comments will be moderated before it appears here.