Firing Squad Problem


By choosing appropriate rules, it is possible to achieve many forms of synchronization within cellular automata. One version, known as the firing squad synchronization problem, was introduced by J. Myhill in 1957, although the first published reference did not appear until five years later (Moore 1962). The firing squad synchronization problem seeks to determine a rule in which all cells in a region go into a special state after the same number of steps. The problem was first solved by Moore (1962). A solution using six colors and a minimal number of steps, illustrated above, was subsequently discovered by Mazoyer (1988), who also determined that no similar four-color solutions exist (Wolfram 2002, p. 1035).

See also

Cellular Automaton

Explore with Wolfram|Alpha


Mazoyer, J. "An Overview of the Firing Squad Synchronization Problem." In Automata Networks: Proceedings of the Fourteenth LITP Spring School on Theoretical Computer Science held in Argelès-Village, May 12-16, 1986 (Ed. C. Choffrut). Berlin: Springer-Verlag, pp. 82-94, 1988.Moore, E. F. Sequential Machines: Selected Papers. Reading, MA: Addison-Wesley, pp. 213-214, 1962.Wolfram, S. A New Kind of Science. Champaign, IL: Wolfram Media, p. 1035, 2002.

Referenced on Wolfram|Alpha

Firing Squad Problem

Cite this as:

Weisstein, Eric W. "Firing Squad Problem." From MathWorld--A Wolfram Web Resource.

Subject classifications