Firing squad synchronization problem

The firing squad synchronization problem is a problem in computer science and cellular automata in which the goal is to design a cellular automaton that, starting with a single active cell, eventually reaches a state in which all cells are simultaneously 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 t such that every cell transitions to the firing state at time t, and such that no cell belongs to the firing state prior to time t. The first solution to the FSSP was found by John McCarthy and Marvin Minsky and was published in Sequential Machines by Moore.

The firing squad synchronization problem has been generalized to many other types of cellular automaton, including higher-dimensional arrays of cells (Shinahr 1974).

Variants of the problem with different initial conditions have also been considered (Kobayashi & Goldstein 2005).

For instance, Patrick Fischer (1965) designed a cellular automaton algorithm to generate the prime numbers based on an earlier solution to the firing squad synchronization problem.

One solution to the FSSP using 15 states and 3n units of time. Time increases from top to bottom.
A solution using 2n-2 units of time. Time increases from bottom to top.