Automata Theory

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.

[top]

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, finite-state 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.

[top]

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 2n-2 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 least-time 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₀ - propagates left
  • R₁ - propagates right
• B: the state that generates the P state
  • B₀ - blocks the R state
  • B₁ - 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₀ - generates A_0xx
  • P₁ - generates A_1xx
• A: the propagating state
  • A₀₀₀, A₁₁₁, A₀₁₀, A₀₁₁, A₁₀₀, A₁₀₁, A₁₁₀, ₁₁₁
  • 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:

1. 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.
2. Every machine with an even A signal generates a new R signal that travels in the opposite direction of the machines A signal
3. 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
4. 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 machine
1	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

[top]

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₀ 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₁ 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₀ STATE

	γ
γ	Q
B0	B1
B1	B0
P	B0

THE R₁ STATE

	B, P'	B0	B1	P
γ	Q	B1	B0	B0

THE P₀ STATE

	P', φ'	P	φ
φ, P	P0	P0	P0
P	P0	T	T
φ	P0	T

THE P₁ STATE

	P', φ'	P	φ
φ,  P	P1	P1	P1
P	P1	T	T
φ	P1	T

THE A₀₀₀ STATE

	P'	PO
γ	Q	B0

THE A₀₀₁ STATE

	γ
γ	Q

THE A₁₀₀ STATE

	γ
B'	R1
B	P1

THE A₁₀₁ STATE

	γ
B'	Q
B	PO

THE A₀₁₀ STATE

	γ
P0'	Q
P0	BO

THE A₀₁₁ STATE

	γ
γ	Q

THE A₁₁₀ STATE

	B'	B
γ	R0	P1

THE A₁₁₁ 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 (2n-2), 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, 2n-2 minimal-time, 192 soldiers, 16 states	Balzer, 2n-2 minimal-time, 160 soldiers, 8 states	Mazoyer, 2n-2 minimal-time, 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 2n-2-k. (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'-2-k'.
  
• According to this setup, in order for the first soldier to receive a signal from the th soldier, a total of 2n'-2-k' 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'-2-k' 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'-2-k' 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 = 2n-2-k 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 n-1 soldiers are arranged in a closed ring.

Result 1: If the ring is a two-way signaling synchronized ring, the minimal time solution is n-1.

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 2n-2, it makes sense that a bi-directional solution should take half as much time.

Result 2: If the ring is a one-way signaling synchronized ring, the minimal time solution is 2n-2.

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 one-way, the ring is equivalent to a straight line with the general at one end. This straight-line equivalence makes the problem the same as the original one, and the solution therefore also takes at least 2n-2 units of time.

(For detailed proofs, see the original text.)

[top]