Recently, a student and I have been working through Waksman's paper ``An Optimum Solution to the Firing Squad Synchronization Problem.'' The paper claims that for any value of $n$, the proposed cellular automaton will reach a synchronized state with all cells in the same state in time $t = 2n - 2$ steps.
We were surprised that for $n = 4$ (a general and three soldiers), our calculations gave this: $$\begin{array}{|c|c|c|c|} P_0 & Q & Q & Q \\ P_0 & A_{010} & Q & Q \\ P_0 & B_0 & A_{011} & Q \\ P_0 & B_0 & Q & P_1 \\ P_0 & B_0 & Q & P_1 \end{array} $$ so that $(P_0, B_0, Q, P_1)$ is a fixed point and the soldiers never reach the synchronized ``all firing'' state promised in the paper. The student wrote a program to check, and it seems that there are many other values of $n$ for which the cells are not synchronized at time $t = 2n - 2$. We were wondering if anyone else had noticed or could verify this.
It's clear that there are some minor misprints in the tables ($\varphi$ instead of $\Phi$ for the wall state, and $\varphi$ instead of $\overline{\varphi}$ in the table for $P_0$). But this seems more fundamental ,and either we are simply mistaken in our calculations/understanding, or some other parts of the solution are not accurate. Any clarification is appreciated.
