Solutions
The first solution to the FSSP was found by John McCarthy and Marvin Minsky and was published in Sequential Machines by Moore. Their solution involves propagating two waves down the line of soldiers: a fast wave and a slow wave moving three times as slow. The fast wave bounces off the other end of the line and meets the slow wave in the centre. The two waves then split into four waves, a fast and slow wave moving in either direction from the centre, effectively splitting the line into two equal parts. This process continues, subdividing the line until each division is of length 1. At this moment, every soldier fires. This solution requires 3n units of time for n soldiers.
A solution using a minimal amount of time was later found by Eiichi Goto (1962); his solution used thousands of states, but required only 2n − 2 units of time for n soldiers. A solution using a smaller amount of time cannot exist. Waksman (1966) improved this solution, using the same amount of time but only 16 states. Balzer (1967) further improved it to eight states, and proved that no four-state solution exists; Peter Sanders later found that Balzer's search procedure was incomplete, but managed to reaffirm the four-state non-existence result through a corrected search procedure. Finally, the best currently known solution, a minimal-time solution using six states, was introduced by Jacques Mazoyer (1987). It is still unknown whether a five-state solution exists.
In the minimal-time solutions, the general sends to the right signals S1, S2, S3, ..., Si at speeds 1, 1/3, 1/7, ..., 1/(2 i−1 − 1). The signal S1 reflects at the right end of the line, and meets signal Si (for i ≥ 2) at cell n/2 i−1. When S1 reflects, it also creates a new general at the right end. Signals Si are constructed using auxiliary signals, which propagate to the left. Every second time a signal moves (to the right), it sends an auxiliary signal to the left. S1 moves on its own at speed 1 while each of the slower signals moves only when it gets an auxiliary signal.
Read more about this topic: Firing Squad Synchronization Problem
Famous quotes containing the word solutions:
“Science fiction writers foresee the inevitable, and although problems and catastrophes may be inevitable, solutions are not.”
—Isaac Asimov (1920–1992)
“The anorexic prefigures this culture in rather a poetic fashion by trying to keep it at bay. He refuses lack. He says: I lack nothing, therefore I shall not eat. With the overweight person, it is the opposite: he refuses fullness, repletion. He says, I lack everything, so I will eat anything at all. The anorexic staves off lack by emptiness, the overweight person staves off fullness by excess. Both are homeopathic final solutions, solutions by extermination.”
—Jean Baudrillard (b. 1929)
“Those great ideas which come to you in your sleep just before you awake in morning, those solutions to the world’s problems which, in the light of day, turn out to be duds of the puniest order, couldn’t they be put to some use, after all?”
—Robert Benchley (1889–1945)