Firing Squad Problem

Myhill posed the firing squad synchronization problem in 1957. You are given a row of soldiers, each of which can be in a finite number of states. The state transition for each soldier occurs simultaneously, and can be recorded as steps 0, 1, .... At each time step, each soldier's successor state is a function of its current state and the current states of its 2 neighboring soldiers. The state transition function is identical for all soldiers who are not at the ends of the row. Indeed, the transition function for each of the end soldiers may be different. Clearly, the endpoint soldiers each have only 1 neighbor.

This row of finite state machines is called a cellular automaton.

Three of the soldiers' states are called the quiescent, excited, and firing states. At time 0, all soldiers are in the quiescent states, except for 1 soldier at an end, who is in the excited state. The problem is to arrange the soldiers' state sets and transition functions such that for this starting position, no matter how many soldiers you start with, all soldiers will, at some future time, enter their firing states on the same step.

This problem has no relation to anyone's grade for the course. It simply is for those who like challenges. Do not hand anything in. It is purely for your personal enjoyment. If you would like a hint, just ask.