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