# Errors in Waksman's Solution to Cellular Automaton Firing Squad Problem?

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.

• By doing an Internet search I find a snippet with author H. Umeo and mentioning errors, presumably of Waksmans paper. You might try finding and reading that paper. Gerhard "Use A Citation Search Also" Paseman, 2018.05.11. Commented May 11, 2018 at 20:27