One solution to the FSSP using 15 states and 3n units of time.

The Firing Squad Synchronization Problem is a problem in computer science and cellular automata first proposed by John Myhill in 1957 and published (with a solution) in 1962 by Edward Moore. The problem is analogous to problems of logical design, systems design, and programming, and can be stated as follows: Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ... A cellular automaton (plural: cellular automata) is a discrete model studied in computability theory, mathematics, and theoretical biology. ... John R. Myhill is a mathematician. ... Edward F. Moore proposed Artificial Living Plants, which would be floating factories which could create copies of themselves. ... Systems design is the process or art of defining the hardware and software architecture, components, modules, interfaces, and data for a computer system to satisfy specified requirements. ... Computer programming (often shortened to programming or coding) is the process of writing, testing, and maintaining the source code of computer programs. ...

Consider a finite amount - but arbitrarily many - of identical finite state machines (soldiers) arranged in a line. At time t = 0, every soldier is initialized to the same state, except for the soldier on the far left (the general). At every time t > 0, the state of every soldier is dependent upon its state and the state of its two neighbors at time t − 1 (except for the two soldiers at either end, whose state depends only upon itself and its one neighbor). In addition, a soldier cannot change state at time t if its state and its neighbors' states at time t − 1 is equal to the initial state. The problem is to define such a set of rules for the soldiers such that all soldiers enter for the first time a distinguished state (fire) at the same time.

Fig. ... In information processing, a state is the complete set of properties (for example, its energy level, etc. ...

History of the Problem

The first solution to the FSSP was found by John McCarthy and Marvin Minsky and was published in Sequential Machines by Moore. A solution using a minimal amount of states was introduced by Jacques Mazoyer in 1988, whose solution uses only six states. In addition, he also proved that no four state solution exists, although the existence of a five state solution is still unknown. John McCarthy (born September 4, 1927, in Boston, Massachusetts, sometimes known affectionately as Uncle John McCarthy), is a prominent computer scientist who received the Turing Award in 1971 for his major contributions to the field of Artificial Intelligence. ... Marvin Lee Minsky (born August 9, 1927), sometimes affectionately known as Old Man Minsky, is an American cognitive scientist in the field of artificial intelligence (AI), co-founder of MITs AI laboratory, and author of several texts on AI and philosophy. ... Edward F. Moore proposed Artificial Living Plants, which would be floating factories which could create copies of themselves. ...

A solution using a minimal amount of time was later found by Professor E. Goto at M.I.T., whose solution uses thousands of states and requires exactly 2n − 2 units of time for n soldiers. It is proven that a solution using a smaller amount of time cannot exist. The Massachusetts Institute of Technology (MIT) is a private, coeducational research university located in Cambridge, Massachusetts. ...

General Solution

A general solution to the FSSP 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 number of soldiers.

Generalizations

Several generalizations of the FSSP have been conjectured and studied, including the FSSP on one-dimensional lines with the general at an arbitrary location, closed rings, Cayley graphs, squares, rectangles, cubes, and general networks. The Cayley graph of the free group on two generators a and b In mathematics, a Cayley graph, named after Arthur Cayley, is a graph that encodes the structure of a group. ... A pictorial representation of a graph In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. ...

External Links

• [1] "Firing Squad Problem"
• [2] "On Formulations of Firing Squad Synchronization Problems"
• [3] "Firing squad synchronization"