stan@hare.DEC (Stanley Rabinowitz) (05/25/84)
THE BRITISH SOLDIERS PROBLEM.
I believe this problem was originally posed by Conway.
I'm sure you will enjoy it. If no one comes up with a solution,
I'll post a solution in a few weeks.
You have n British soldiers in a line. Each soldier is initially
at rest. Each soldier is identical and his actions can be described
by a finite state automaton. A soldier's new state depends only
on his previous state and the previous state of the two soldiers
next to him. (The two soldiers on the end have fictitious neighbors
to one side who are always in the fictitious state.)
Your problem is to design the states (e.g. rest, at ease, ready, attention,
aim, etc.) and the state transitions, so that it is possible for a sargeant
to come over and order one guy on the end into the attention state and so that
this will eventually cause all the soldiers to fire their guns
simultaneously. No gun may fire prior to this occurrence.
You may only specify a finite number of states.
Your solution must work regardless of the value of n.
(In particular, I may line up more soldiers than you have states.)
---------------------------------
[Be sure to test any alleged solutions first via a computer simulation.]
I would also be interested in any references to this problem in the
literature.
Stanley Rabinowitz
Digital Equipment Corporation
Nashua, NH
UUCP: ...{decvax,ucbvax,allegra}!decwrl!rhea!hare!stan
ARPA: stan%hare.DEC@DECWRL.ARPA
USPS: 6 Country Club Lane, Merrimack, NH 03054smh@mit-eddie.UUCP (Steven M. Haflich) (05/26/84)
This problem is also known as the "firing squad synchronization problem." It appears as a problem in Marvin Minsky [Computation: Finite and Infinite Machines] (1967) who quotes the problem verbatim from Edward Moore [Sequential Machines: selected Papers] (1964). A brief synopsis: Moore claimed the problem was originaly devised about 1957 by John Myhill, and was first solved by John McCarthy and Minsky. Moore claims that once the problem was known to have a solution, almost everyone can solve it. He emphasizes the beauty of working out the problem for oneself, so I will not spoil the trick. Moore adds, however, that most people do not come close to the minimal-time solution, which for N soldiers has the firing occur 2N-2 clock ticks after the order is given. Minsky discusses the nature of the solution (without giving it completely) "in the back of the book." If urged, I could be convinced to post a similar description in a couple weeks. Steven Haflich, MIT