Firing Squad Problem
Alternate name
Definition
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. 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. A solution using six colors and a minimal number of steps, illustrated above, was subsequently discovered by Mazoyer, who also determined that no similar four-color solutions exist.
Related term
