![FiringSquadProblem](https://upload.wikimedia.org/wikipedia/commons/9/9a/FiringSquadProblem.svg)
The firing squad synchronization problem is a problem in
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
and
cellular automata
A cellular automaton (pl. cellular automata, abbrev. CA) is a discrete model of computation studied in automata theory. Cellular automata are also called cellular spaces, tessellation automata, homogeneous structures, cellular structures, tessel ...
in which the goal is to design a
cellular automaton
A cellular automaton (pl. cellular automata, abbrev. CA) is a discrete model of computation studied in automata theory. Cellular automata are also called cellular spaces, tessellation automata, homogeneous structures, cellular structures, tessel ...
that, starting with a single active cell, eventually reaches a state in which all cells are simultaneously active. It was first proposed by
John Myhill
John R. Myhill Sr. (11 August 1923 – 15 February 1987) was a British mathematician.
Education
Myhill received his Ph.D. from Harvard University under Willard Van Orman Quine in 1949. He was professor at SUNY Buffalo from 1966 until his death ...
in 1957 and published (with a solution by
John McCarthy and
Marvin Minsky
Marvin Lee Minsky (August 9, 1927 – January 24, 2016) was an American cognitive and computer scientist concerned largely with research of artificial intelligence (AI), co-founder of the Massachusetts Institute of Technology's AI laboratory, an ...
) in 1962 by
Edward F. Moore
Edward Forrest Moore (November 23, 1925 in Baltimore, Maryland – June 14, 2003 in Madison, Wisconsin) was an American professor of mathematics and computer science, the inventor of the Moore machine, Moore finite state machine, and an early pione ...
.
Problem statement
The name of the problem comes from an analogy with real-world
firing squad
Execution by firing squad, in the past sometimes called fusillading (from the French ''fusil'', rifle), is a method of capital punishment, particularly common in the military and in times of war. Some reasons for its use are that firearms are us ...
s: the goal is to design a system of rules according to which an officer can command an execution detail to fire so that its members fire their rifles simultaneously.
More formally, the problem concerns
cellular automata
A cellular automaton (pl. cellular automata, abbrev. CA) is a discrete model of computation studied in automata theory. Cellular automata are also called cellular spaces, tessellation automata, homogeneous structures, cellular structures, tessel ...
, arrays of
finite state machines called "cells" arranged in a line, such that at each time step each machine transitions to a new state as a function of its previous state and the states of its two neighbors in the line. For the firing squad problem, the line consists of a finite number of cells, and the rule according to which each machine transitions to the next state should be the same for all of the cells interior to the line, but the transition functions of the two endpoints of the line are allowed to differ, as these two cells are each missing a neighbor on one of their two sides.
The states of each cell include three distinct states: "active", "quiescent", and "firing", and the transition function must be such that a cell that is quiescent and whose neighbors are quiescent remains quiescent. Initially, at time , all states are quiescent except for the cell at the far left (the general), which is active. The goal is to design a set of states and a transition function such that, no matter how long the line of cells is, there exists a time such that every cell transitions to the firing state at time , and such that no cell belongs to the firing state prior to time .
Solutions
The first solution to the FSSP was found by
John McCarthy and
Marvin Minsky
Marvin Lee Minsky (August 9, 1927 – January 24, 2016) was an American cognitive and computer scientist concerned largely with research of artificial intelligence (AI), co-founder of the Massachusetts Institute of Technology's AI laboratory, an ...
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 3''n'' units of time for ''n'' soldiers.
A solution using a minimal amount of time (which is units of time for soldiers), was first found by , but his solution used thousands of states. improved this to 16 states, and further improved it to eight states, while claiming to prove 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. The best currently known solution, using six states, was introduced by . It is still unknown whether a five-state solution exists.
In the minimal-time solutions, the general sends to the right signals at speeds . The signal reflects at the right end of the line, and meets signal (for ) at cell . When reflects, it also creates a new general at the right end. Signals 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. moves on its own at speed 1 while each of the slower signals moves only when it gets an auxiliary signal.
Generalizations
The firing squad synchronization problem has been generalized to many other types of cellular automaton, including higher-dimensional arrays of cells . Variants of the problem with different initial conditions have also been considered .
Solutions to the firing squad problem may also be adapted to other problems. For instance, designed a cellular automaton algorithm to generate the
prime number
A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
s based on an earlier solution to the firing squad synchronization problem.
References
*.
*.
*. As cited by .
*.
*.
*.
*.
*.
External links
*{{mathworld, title=Firing Squad Problem, urlname=FiringSquadProblem
A visualization and explanation of one of the solutions
Cellular automata
Mathematical problems