Earthcomputer's Website

Firing Squad Problem

Problem Description

The Firing Squad Problem (FSP) is about designing a 1D cellular automaton, with n possible states for each cell, such that all cells will end up in the same state, having never been in that state before. Each cell follows the same set of rules (the "automaton"), which take the previous state of itself and its two neighbors, and outputs the next state for that cell. For cells at the edge, their neighbor is a special "null" state, which does not count to n.

A 6-state solution exists for all possible widths. It has been proven that there is no single 4-state solution for all possible widths, although 4-state solutions exist for powers of 2. It is unknown whether there is a single 5-state solution that works for all widths.

I/O Upload Automaton: Download Automaton: