一斉射撃問題
一斉射撃問題に対する最初の解法は、ジョン・マッカーシーとマービン・ミンスキーにより与えられ、ムーアの Sequential Machines: Selected Papersに収録されて出版された。これは最もオーソドックスな解法であり、兵士の列上を伝搬する2つの「波」が基本的な役割を果たす。1つめの波は「光速」で、もう1つの波はその1/3の速度で伝搬する。片方の端からそのような2つの「波」が発生し、速いほうの波が反対側の端で跳ね返った後、遅いほうの波と衝突した瞬間のことを考えてみよう。その時、兵士の数をnとすると1.5nステップが経過していて、衝突はちょうど中央で起きている。これにより兵士の列は2等分されたことになる。そこで2つの波をそれぞれ、計4つの波に分割し、左右が鏡像になるように同様に繰り返すようにする。等分された各列について再帰的に同様の現象が発生し、最終的に1人ずつに分割されるまで繰り返されたならば特別な状態遷移に入り、全ての兵士が同時に発砲する。この解法はn人の兵士に対して3nステップ前後を必要とする。
最小時間を達成する解法 (兵士 n 人に対して 2n − 2 単位時間)を最初に発見したのは後藤英一(1962)だが、彼の解法は比較的多数の状態を必要とするものであった。 Waksman (1966) がこれを16状態まで改善し、 Balzer (1967) がさらに8状態まで減らした上で、4状態の解法がないことを示したと主張した。
一斉射撃問題は多くの異なる種類のセル・オートマトンに一般化されてきた。例えば、Shinahr (1974)では高次元の配列に一般化されている。初期条件の異なる亜種も検討されている(Kobayashi & Goldstein 2005)。
一斉射撃問題の解法は他の問題にも適応させられる場合がある。例えば、 Patrick Fischer (1965) は、一斉射撃問題に対する初期の解法をもとに、素数を生成するセル・オートマトンのアルゴリズムを設計した。