Elementary cellular automaton
In mathematics and computability theory, an elementary cellular automaton is a one-dimensional cellular automaton where there are two possible states (labeled 0 and 1) and the rule to determine the state of a cell in the next generation depends only on the current state of the cell and its two immediate neighbors. As such it is one of the simplest possible models of computation. Nevertheless, there is an elementary cellular automaton (rule 110, defined below) which is capable of universal computation.
There are 8 = 23 possible configurations for a cell and its two immediate neighbors. The rule defining the cellular automaton must specify the resulting state for each of these possibilities so there are 256 = 223 possible elementary cellular automata. Stephen Wolfram proposed a scheme, known as the Wolfram code, to assign each rule a number from 0 to 255 which has become standard. Each possible current configuration is written in order, 111, 110, ..., 001, 000, and the resulting state for each of these configurations is written in the same order and interpreted as the binary representation of an integer. This number is taken to be the rule number of the automaton. For example, 110d=96d+14d written in binary is 011011102. So rule 110 is defined by the transition rule:
Although there are 256 possible rules, many of these are trivially equivalent to each other up to a simple transformation of the underlying geometry. The first such transformation is reflection through a vertical axis and the result of applying this transformation to a given rule is called the mirrored rule. These rules will exhibit the same behavior up to reflection through a vertical axis, and so are equivalent in a computational sense.
For example, if the definition of rule 110 is reflected through a vertical line, the following rule (rule 124) is obtained:
Rules which are the same as their mirrored rule are called amphichiral. Of the 256 elementary cellular automata, 64 are amphichiral.
The second such transformation is to exchange the roles of 0 and 1 in the definition. The result of applying this transformation to a given rule is called the complementary rule. For example, if this transformation is applied to rule 110, we get the following rule
...
Wikipedia