The Firing Squad Problem
Introduction
In 1957, John Myhill first posed an interesting problem that was closely related to computer programming, but did not require any related background to solve. Dubbed the "firing squad synchronization problem," the puzzle was passed along by word of mouth and first solved by Marvin Minsky and John McCarthy. However, even though it was widely known and had already been solved, it wasn't until years later, in 1964, that Edward Moore at Bell Telephone Laboratories published a short paper establishing the question in print. Since then, many have found solutions of varying complexity and elegance, as well as posed and solved different variations of the original question. Today, the firing squad problem is featured in most discussions of automata theory, and increasingly efficient solutions are still being explored.
The Problem
Picture a group of soldiers standing in a line, with a general at one end. Assume that all of the soldiers are mentally keeping track of time by counting at the same speed. In other words, after a certain signal, all soldiers should be counting out zero, one, two, and so forth, at the same time as everyone else. At every count, each soldier looks at their neighbors, considers what they themselves were already doing, and decides what to do next, completely according to what they see. Of course, the two soldiers on the ends have to act according to what themselves and their one neighbor is doing. In more mathematical terms, the actions, or state, of each soldier at time t+1 depend on the actions of itself and its neighbors at the previous time t. For all soldiers, there is a limited, or finite, amount of actions that can be done, and there are set rules for finding out which actions follow given observations. Using technical terms, the soldiers can be seen as synchronous, finitestate machines, whose states at any given time are dependant only upon themselves and their neighbors.
The concept of synchronization arises when the initial state of a machine is known or partially unknown, yet the task requires that the machine be brought to a specified final state. In this case, it is first necessary to bring the machine to a known, intermediate state, identified by a resulting output sequence. As soon as the intermediate state is identified, a second input sequence is selected, and the machine is sent to the desired final state. For some machines, it is possible to use one sequence to take the machine from the unknown initial state to the known final state. In this case, the input sequence is known as a synchronizing sequence, and the synchronizing problem is considered solvable.
The question begins when the general gives the signal to fire, and does not do anything else. Assume all of the soldiers start off in the same, inactive, state, called the quiescent state. After a count of time, the soldier closest to the general reacts to the signal by changing what its doing, equivalent to a machine changing its state. As time goes by, the signal propagates down the line, moving at most one soldier per count. Of course, each individual soldier might be changing their own state according to the states of themselves and their neighbors. Assuming that there is a fixed number of states, regardless of how many soldiers there are in the line, how can the states be defined such that all soldiers enter the same firing, or terminal, state at the exact same time? In other words, the same definitions for the states should still work even if the number of soldiers is dramatically increased.
Minimal Time Solution
If there are n soldiers in line, including the general, and signals propagate down the line with the fastest speed of at most one soldier at a time, it is clear that any solution must take at least 2n2 units of time (the amount of time for a signal to travel all the way down the line and back). Although others may have solved for such a solution at an earlier date, Abraham Waksman's leasttime solution published in 1966 (source) is often considered one of the first, and will be explored below.
There are six basic states, four of which have subdivisions:
 Q: the starting quiescent state
 T: the final firing state
 R: the trigger signal for the B state
 R_{0}  propagates left
 R_{1}  propagates right
 B: the state that generates the P state
 B_{0}  blocks the R state
 B_{1}  passes through the R state
 P: the state that generates the A state, and leads to the terminal state if both neighbors are also in the P state
 P_{0}  generates A_{0xx}
 P_{1}  generates A_{1xx}
 A: the propagating state
 A_{000}, A_{111}, A_{010}, A_{011}, A_{100}, A_{101}, A_{110}, _{111}
 A_{0xx}  generates the R state with no delay
 A_{1xx}  has a one unit time delay in R generation
 All A_{x00} and _{x01}  propagates to the left
 All A_{x10} and _{x11}  propagates to the right
There are two additional placeholder states:
 φ: external state, no machine to this side
 γ: neighbors not explicitly mentioned
For comprehensive state tables, see the following section.
To better understand how the states interact, Waksman provides a basic explanation of how his solution works (source):
Some facts:
 Every A signal can be called either even or odd based on whether it is currently at an even or odd machine. The parity is determined starting from the machine which originally generated the signal.
 Every machine with an even A signal generates a new R signal that travels in the opposite direction of the machines A signal
 Each type of B signal will switch to the other type upon intersection with an R signal. One type allows the R signal to continue propagating, the other does not
 When signals A and B intersect, they set up a new generator, or P signal
Since, as seen in fact 2, every second machine in state A generates a new R signal traveling in the opposite direction, there is a 3 unit time separation between two R signals traveling through the same machine.
Basically, each machine that enters the B state will remain in that state for three time units, until an R signal reaches it. At that time, the B state will move to the next machine in a direction opposing the R signal.
Seeing as how the number of soldiers can be arbitrarily large, an efficient system of dividing up the line of soldiers is needed. For each division of the line, the signal must propagate through at a certain time delay so that signals returning from the end of the line will coincide at the right moment, allowing all soldiers to fire at the same time. From the aforementioned observations, Waksman derived a formula for determining how much of a time unit delay was needed per machine, given the number of divisions:
divisions
time unit delay per machine1
2(2 ^{1  1}) + 1
3
2
2(2 ^{2  1}) + 1
7
3
2(2 ^{3  1}) + 1
15
4
2(2 ^{4  1}) + 1
31
k
2(2 ^{k  1}) + 1
2 ^{k+1}  1
Therefore, the B_{k} signal must have a time unit delay per machine, or rate of propagation, of 1/(2 ^{k+1}  1) for k divisions.
Here is a charted example of a solution:
State results for n = 11 (soldiers)
Columns represent soldiers, rows represent units of time
States: Q T R B P A
1
2
3
4
5
6
7
8
9
10
11
0
P0
Q
Q
Q
Q
Q
Q
Q
Q
Q
Q
1
P0
A010
Q
Q
Q
Q
Q
Q
Q
Q
Q
2
P0
B0
A011
Q
Q
Q
Q
Q
Q
Q
Q
3
P0
B0
Q
A010
Q
Q
Q
Q
Q
Q
Q
4
P0
B0
R0
Q
A011
Q
Q
Q
Q
Q
Q
5
P0
R0
B1
Q
Q
A010
Q
Q
Q
Q
Q
6
P0
B0
B1
Q
R0
Q
A011
Q
Q
Q
Q
7
P0
B0
B1
R0
Q
Q
Q
A010
Q
Q
Q
8
P0
B0
Q
B0
Q
Q
R0
Q
A011
Q
Q
9
P0
B0
Q
B0
Q
R0
Q
Q
Q
A010
Q
10
P0
B0
Q
B0
R0
Q
Q
Q
R0
Q
P0
11
P0
B0
Q
R0
B1
Q
Q
R0
Q
A000
P0
12
P0
B0
R0
Q
B1
Q
R0
Q
A001
B0
P0
13
P0
R0
B1
Q
B1
R0
Q
A000
Q
B0
P0
14
P0
B0
B1
Q
Q
B0
A001
Q
R1
B0
P0
15
P0
B0
B1
Q
Q
P1
Q
Q
B1
R1
P0
16
P0
B0
B1
Q
A100
P1
A110
Q
B1
B0
P0
17
P0
B0
B1
A101
R1
P1
R0
A111
B1
B0
P0
18
P0
B0
P0
P0
B0
P1
B0
P0
P0
B0
P0
19
P0
P0
P0
P0
P0
P1
P0
P0
P0
P0
P0
20
T
T
T
T
T
T
T
T
T
T
T
State Tables
Left neighbor represented by the leftmost column, right neighbor represented by the top row
THE Q STATE
A000 
A001 
A100 
A101 
A010 
A011 
A110 
A111 

Q 
A001 
A000 
A101 
A100 
R0 
Q 
Q 
Q 
B 
A001 
A000 
A101 
A100 
R0 
Q 
Q 
Q 
R0 
A001 
A000 
A101 
A100 
Q 
Q 
Q 
Q 
R1 
A001 
A000 
A101 
A100 

P0 
B0 

P1 
B0 

φ 
P0 
P1 
P0 
P1 
Q 
B 
R0 
R1 
P0 
P1 
φ 

A000 
R1 
R1 

A001 
Q 
Q 
Q 
B0 

A100 
Q 
Q 

A101 
Q 
Q 

A010 
A011 
A011 
P0 

A011 
A010 
A010 
P1 

A110 
A111 
A111 
P0 

A111 
A110 
A110 
P1 

Q 
Q 
Q 
R0 
Q 
A000 
A100 
Q 
γ 
A000 
Q 
B 
R0 
R1 
P0 
P1 
φ 
γ 

B 
Q 
Q 
R0 
Q 
Q 
Q 

R0 
Q 
Q 
A000 
Q 

R1 
R1 
R1 
R1 
R1 

P0 
A010 
Q 
R0 
Q 
P0 
P0 

P1 
A110 
Q 
R0 
Q 
P0 
P0 

φ 
Q 
THE B_{0} STATE
γ 
P 
A000 
A100 
A001 
A101 
R0 

γ 
B0 
B0 
P0 
P1 
P1 
P0 
R0 
P 
B0 
P0 
R0 

A010 
P0 

A110 
P1 

A011 
P1 

A111 
P0 

R1 
R1 
THE B_{1} STATE
γ 
P 
A000 
A100 
A001 
A101 
R0 

γ 
B1 
P0 
P1 
P1 
P0 
Q 

P 
P0 

A010 
P0 

A110 
P1 

A011 
P1 

A111 
P0 

R1 
Q 
THE R_{0} STATE
γ 

γ 
Q 
B0 
B1 
B1 
B0 
P 
B0 
THE R_{1} STATE
B, P' 
B0 
B1 
P 

γ 
Q 
B1 
B0 
B0 
THE P_{0} STATE
P', φ' 
P 
φ 

φ, P 
P0 
P0 
P0 
P 
P0 
T 
T 
φ 
P0 
T 
THE P_{1} STATE
P', φ' 
P 
φ 

φ, P 
P1 
P1 
P1 
P 
P1 
T 
T 
φ 
P1 
T 
THE A_{000} STATE
P' 
PO 

γ 
Q 
B0 
THE A_{001} STATE
γ 

γ 
Q 
THE A_{100} STATE
γ 

B' 
R1 
B 
P1 
THE A_{101} STATE
γ 

B' 
Q 
B 
PO 
THE A_{010} STATE
γ 

P0' 
Q 
P0 
BO 
THE A_{011} STATE
γ 

γ 
Q 
THE A_{110} STATE
B' 
B 

γ 
R0 
P1 
THE A_{111} STATE
B' 
B 

γ 
Q 
P0 
[top]
Solution Comparison
Since the problem's conception, many solutions have been published and a countless number have been found. Some of them take the least time to complete (2n2), others require the least amount of states (6), some do both (Mazoyer's solution), and many others are simply easier to understand. For all of these, the states and soldiers can be represented graphically and then compared. Just by looking at these results, you can see how different numbers of states, time units, and methods, influence how the complexity and flow of a solution (source):
Anonymous, 3n time, 160 soldiers, 13 states 
Waksman, 2n2 minimaltime, 192 soldiers, 16 states 
Balzer, 2n2 minimaltime, 160 soldiers, 8 states 
Mazoyer, 2n2 minimaltime, 200 soldiers, 6 states 
[top]
Variations
Just as there are many different solutions to the problem, numerous variations to the question have been posed and solved. Here, a few changes to the positions of the soldiers are explored and analyzed.
Original problem: N soldiers, including the general, are in a straight line. The general is placed at one end of the line.
Moore and Langdon's generalization: The general can be anywhere along the line.
In a line of n soldiers, including the general, let k represent the number of soldiers between the general and the nearest end. (According to this definition, k can never be greater than (n+1)/2  1.
Theorem: In the general case as defined above, the amount of time needed for the line to fire at the same time is at least 2n2k. (When the general is at the end, k is 0 and the theorem still holds.)
Proof by contradiction:
 For a given k, assume the general is somewhere on the left side of the line, at position k+1.
 Now assume there is a line of soldiers, S, where k is an integer and 1 ≤ k ≤ (n+1)/2  1, where n is an arbitrary number of soldiers (including the general). This line, S, has length n' and the general at position k'+1.
 Now assume that for this line, S, the firing squad is able to fire at time t = m, where m < 2n'2k'.
 According to this setup, in order for the first soldier to receive a signal from the th soldier, a total of 2n'2k' units of time must pass (n'1 k' units for the signal to travel from general to n', plus n'1 units for the signal to travel back from n' to 1).
 However, the total time m is less than this amount, meaning the first soldier managed to enter the firing state without ever having received a signal from the n'th soldier.
 Thus, the first soldier fires without any influence from any soldiers including and beyond the n'th one.
 Now if we were to add on n'+2 more soldiers to the right of the line, the first soldier would still fire at the original time, m. This is true because with regard to the first soldier, nothing about the line or states has changed.
 Yet, since m < 2n'2k' as defined above, the 2n'+2 soldier is still in the original, quiescent, state while the first soldier is already firing.
 Therefore, the line S cannot represent a valid solution, which contradicts the original premise, and m < 2n'2k' cannot be true.
 By mutatis mutandis, or substituting the appropriate terms as necessary, this proof can be applied to all possible placements of the general.
Once the above proof established a minimum value for the solution, results that take time t = 2n2k are found and analyzed. The problem becomes equivalent to assuming the general started at the end at a time k units ago, and is solved by continuing the signal propagation.
Karel Culik's theorems: One general and n1 soldiers are arranged in a closed ring.
Result 1: If the ring is a twoway signaling synchronized ring, the minimal time solution is n1.
Although the proof itself is somewhat involved and builds upon some earlier results, this idea makes intuitive sense. Basically, if for a straight line, where signals travel along that line, the solution takes 2n2, it makes sense that a bidirectional solution should take half as much time.
Result 2: If the ring is a oneway signaling synchronized ring, the minimal time solution is 2n2.
Again, the actual proof is best described by Culik itself, but similar to Result 1, this also makes sense. Since the signals only travel along oneway, the ring is equivalent to a straight line with the general at one end. This straightline equivalence makes the problem the same as the original one, and the solution therefore also takes at least 2n2 units of time.
(For detailed proofs, see the original text.)