Problem Statement
The name of the problem comes from an analogy with real-world firing squads: the goal is to design a system of rules according to which a general can command a squad of troops to fire, and cause them to all fire their guns simultaneously.
More formally, the problem concerns cellular automata, arrays of finite state machines called "cells" arranged in a line, such that at each time step each machine transitions to a new state as a function of its previous state and the states of its two neighbors in the line. For the firing squad problem, the line consists of a finite number of cells, and the rule according to which each machine transitions to the next state should be the same for all of the cells interior to the line, but the transition functions of the two endpoints of the line are allowed to differ, as these two cells are each missing a neighbor on one of their two sides.
The states of each cell include three distinguished states: "active", "quiescent", and "firing", and the transition function must be such that a cell that is quiescent and whose neighbors are quiescent remains quiescent. Initially, at time t = 0, all states are quiescent except for the cell at the far left (the general), which is active. The goal is to design a set of states and a transition function such that, no matter how long the line of cells is, there exists a time t such that every cell transitions to the firing state at time t, and such that no cell belongs to the firing state prior to time t.
Read more about this topic: Firing Squad Synchronization Problem
Famous quotes containing the words problem and/or statement:
“If we parents accept that problems are an essential part of life’s challenges, rather than reacting to every problem as if something has gone wrong with universe that’s supposed to be perfect, we can demonstrate serenity and confidence in problem solving for our kids....By telling them that we know they have a problem and we know they can solve it, we can pass on a realistic attitude as well as empower our children with self-confidence and a sense of their own worth.”
—Barbara Coloroso (20th century)
“The new statement will comprise the skepticisms, as well as the faiths of society, and out of unbeliefs a creed shall be formed. For, skepticisms are not gratuitous or lawless, but are limitations of the affirmative statement, and the new philosophy must take them in, and make affirmations outside of them, just as much as must include the oldest beliefs.”
—Ralph Waldo Emerson (1803–1882)