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).

REFERENCES:

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.