Myhill posed the firing squad synchronization problem in 1957. In this problem, you are given a row of soldiers, each of which can be in a finite number of states. A clock provides a sequence of time steps, 0, 1, 2, and so on; at each positive time step, the state of each soldier is set to a function, the transition function, of its previous state and the adjacent soldiers' previous states. This function is identical for all soldiers not at the ends of the row; the end soldiers, however, may have different transition functions. (Nowadays this would be called a `cellular automaton'.)
Three of the soldiers' states are called the quiescent, excited, and firing states. At time 0, all soldiers are in their quiescent states, except for one soldier at an end, who is in his excited state. The problem is to arrange the soldiers' state sets and transition functions such that for this starting position, no matter how many soldiers you start with, all soldiers will, at some future time, enter their firing states simultaneously.
Try to solve the problem now, or read on for the solution.
Back to the home page
David Moews ( dmoews@fastmail.fm )
Last significant update 20-IX-2004