一斉射撃問題

http://klibredb.lib.kanagawa-u.ac.jp/dspace/handle/10487/1326
一斉射撃問題とは、1957年にJohn Myhillにより提案された、「有限状態の1次元セルオートマトン」が同期するためのアルゴリズムを見付ける問題。
セルの一つを将軍とし、それ以外を兵士とする。将軍が射撃命令を下すことにより、将軍を含め兵士全員が、同時刻で射撃状態に移行するように、兵士たちの状態遷移関数を構成する。
なお、いくつかの条件があり、情報伝達は将軍、兵士とも1ステップに両隣にしか伝えられない、兵士は一斉射撃になるまでは、射撃状態に入ってはけない、などの制約がある。
これにはいくつかの解法が知られている。
セルの取りうる状態数よりも大きいセル数でも一斉射撃ができなければならないため、単純には解決できない。