一斉射撃問題
一斉射撃問題 (firing squad synchronization problem) という名前は、現実世界の銃殺隊 (firing squad) の類推から来ている: この問題の目標は、銃殺隊のように、1人の「将校」の「指令」から始まって、全ての「兵士」が同時にライフルを発砲するような、セル・オートマトンを構成することである。
以下ではより形式的に記述する。これは1次元のセル・オートマトン、すなわち、一直線に並んだ有限オートマトンの列であり、その一つ一つのオートマトンを「セル(細胞)」と呼ぶ。
他の種類の1次元セル・オートマトンでも一般的なルールとしては、各セルは離散的な状態を持ち、1ステップごとに同時に(一斉に)それぞれの次の状態に遷移する。各セルの次の状態は、自分自身のその時の状態と隣接する2つのセルの状態とのみから計算される。というルールがある。
一斉射撃問題では、さらに、全体は連続した有限個のセルからなり、どの位置のセルも同じ規則に従って遷移する(端については、後述する制限を除いて、特別扱いがあってよい)。
セルの状態には、3つの特別な状態、「休止」「指令」「発砲」が問題の側で用意される(解答者は必要なだけ状態を追加して、解答を考える)。