The firing squad synchronization problem is a problem in computer science and cellular automata in which the goal is to design a cellular automaton that, starting with a single active cell, eventually reaches a state in which all cells are simultaneously active. It was first proposed by John Myhill in 1957 and published (with a solution by John McCarthy and Marvin Minsky) in 1962 by Edward F. Moore.
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 an officer can command an execution detail to fire so that its members fire their rifles 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 distinct 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.
The first solution to the FSSP was found by John McCarthy and Marvin Minsky and was published in Sequential Machines by Moore. Their solution involves propagating two waves down the line of soldiers: a fast wave and a slow wave moving three times as slow. The fast wave bounces off the other end of the line and meets the slow wave in the centre. The two waves then split into four waves, a fast and slow wave moving in either direction from the centre, effectively splitting the line into two equal parts. This process continues, subdividing the line until each division is of length 1. At this moment, every soldier fires. This solution requires 3n units of time for n soldiers.
A solution using a minimal amount of time (which is 2n − 2 units of time for n soldiers), was first found by EiichiGoto ( 1962 ), but his solution used thousands of states. Waksman (1966) improved this to 16 states, and Balzer (1967) further improved it to eight states, while claiming to prove that no four-state solution exists. Peter Sanders later found that Balzer's search procedure was incomplete, but managed to reaffirm the four-state non-existence result through a corrected search procedure. The best currently known solution, using six states, was introduced by JacquesMazoyer ( 1987 ). It is still unknown whether a five-state solution exists.
In the minimal-time solutions, the general sends to the right signals S1, S2, S3, ..., Si at speeds 1, 1/3, 1/7, ..., 1/(2 i−1 − 1). The signal S1 reflects at the right end of the line, and meets signal Si (for i ≥ 2) at cell n/2 i−1. When S1 reflects, it also creates a new general at the right end. Signals Si are constructed using auxiliary signals, which propagate to the left. Every second time a signal moves (to the right), it sends an auxiliary signal to the left. S1 moves on its own at speed 1 while each of the slower signals moves only when it gets an auxiliary signal.
The firing squad synchronization problem has been generalized to many other types of cellular automaton, including higher-dimensional arrays of cells ( Shinahr 1974 ). Variants of the problem with different initial conditions have also been considered ( Kobayashi & Goldstein 2005 ).
Solutions to the firing squad problem may also be adapted to other problems. For instance, PatrickFischer ( 1965 ) designed a cellular automaton algorithm to generate the prime numbers based on an earlier solution to the firing squad synchronization problem.
The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970. It is a zero-player game, meaning that its evolution is determined by its initial state, requiring no further input. One interacts with the Game of Life by creating an initial configuration and observing how it evolves. It is Turing complete and can simulate a universal constructor or any other Turing machine.
A cellular automaton is a discrete model of computation studied in automata theory. Cellular automata are also called cellular spaces, tessellation automata, homogeneous structures, cellular structures, tessellation structures, and iterative arrays. Cellular automata have found application in various areas, including physics, theoretical biology and microstructure modeling.
An excitable medium is a nonlinear dynamical system which has the capacity to propagate a wave of some description, and which cannot support the passing of another wave until a certain amount of time has passed.
In a cellular automaton, a Garden of Eden is a configuration that has no predecessor. It can be the initial configuration of the automaton but cannot arise in any other way. John Tukey named these configurations after the Garden of Eden in Abrahamic religions, which was created out of nowhere.
In automata theory, a permutation automaton, or pure-group automaton, is a deterministic finite automaton such that each input symbol permutes the set of states.
In computer science, a linear bounded automaton is a restricted form of Turing machine.
Von Neumann cellular automata are the original expression of cellular automata, the development of which was prompted by suggestions made to John von Neumann by his close friend and fellow mathematician Stanislaw Ulam. Their original purpose was to provide insight into the logical requirements for machine self-replication, and they were used in von Neumann's universal constructor.
A block cellular automaton or partitioning cellular automaton is a special kind of cellular automaton in which the lattice of cells is divided into non-overlapping blocks and the transition rule is applied to a whole block at a time rather than a single cell. Block cellular automata are useful for simulations of physical quantities, because it is straightforward to choose transition rules that obey physical constraints such as reversibility and conservation laws.
John R. Myhill Sr. was a British mathematician.
In computer science, in particular in automata theory, a two-way finite automaton is a finite automaton that is allowed to re-read its input.
Bursting, or burst firing, is an extremely diverse general phenomenon of the activation patterns of neurons in the central nervous system and spinal cord where periods of rapid action potential spiking are followed by quiescent periods much longer than typical inter-spike intervals. Bursting is thought to be important in the operation of robust central pattern generators, the transmission of neural codes, and some neuropathologies such as epilepsy. The study of bursting both directly and in how it takes part in other neural phenomena has been very popular since the beginnings of cellular neuroscience and is closely tied to the fields of neural synchronization, neural coding, plasticity, and attention.
Quantum dot cellular automata are a proposed improvement on conventional computer design (CMOS), which have been devised in analogy to conventional models of cellular automata introduced by John von Neumann.
John von Neumann's universal constructor is a self-replicating machine in a cellular automaton (CA) environment. It was designed in the 1940s, without the use of a computer. The fundamental details of the machine were published in von Neumann's book Theory of Self-Reproducing Automata, completed in 1966 by Arthur W. Burks after von Neumann's death. While typically not as well known as von Neumann's other work, it is regarded as foundational for automata theory, complex systems, and artificial life. Indeed, Nobel Laureate Sydney Brenner considered Von Neumann's work on self-reproducing automata central to biological theory as well, allowing us to "discipline our thoughts about machines, both natural and artificial."
The majority problem, or density classification task, is the problem of finding one-dimensional cellular automaton rules that accurately perform majority voting.
Rule 184 is a one-dimensional binary cellular automaton rule, notable for solving the majority problem as well as for its ability to simultaneously describe several, seemingly quite different, particle systems:
In the mathematical study of cellular automata, Rule 90 is an elementary cellular automaton based on the exclusive or function. It consists of a one-dimensional array of cells, each of which can hold either a 0 or a 1 value. In each time step all values are simultaneously replaced by the exclusive or of their two neighboring values. Martin, Odlyzko & Wolfram (1984) call it "the simplest non-trivial cellular automaton", and it is described extensively in Stephen Wolfram's 2002 book A New Kind of Science.
A reversible cellular automaton is a cellular automaton in which every configuration has a unique predecessor. That is, it is a regular grid of cells, each containing a state drawn from a finite set of states, with a rule for updating all cells simultaneously based on the states of their neighbors, such that the previous state of any cell before an update can be determined uniquely from the updated states of all the cells. The time-reversed dynamics of a reversible cellular automaton can always be described by another cellular automaton rule, possibly on a much larger neighborhood.
Eiichi Goto was a Japanese computer scientist, the builder of one of the first general-purpose computers in Japan.
CoDi is a cellular automaton (CA) model for spiking neural networks (SNNs). CoDi is an acronym for Collect and Distribute, referring to the signals and spikes in a neural network.
The Greenberg–Hastings Cellular Automaton is a three state two dimensional cellular automaton named after James M. Greenberg and Stuart Hastings, designed to model excitable media, One advantage of a CA model is ease of computation. The model can be understood quite well using simple "hand" calculations, not involving a computer. Another advantage is that, at least in this case, one can prove a theorem characterizing those initial conditions which lead to repetitive behavior.