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.Rule 0Rule 1Rule 2Rule 3Rule 4Rule 5Rule 6Rule 7Rule 8Rule 9Rule 10Rule 11Rule 12Rule 13Rule 14Rule 15Rule 18Rule 19Rule 22Rule 23Rule 24Rule 25Rule 26Rule 27Rule 28Rule 29Rule 30Rule 32Rule 33Rule 34Rule 35Rule 36Rule 37Rule 38Rule 40Rule 41Rule 42Rule 43Rule 44Rule 45Rule 46Rule 50Rule 51Rule 54Rule 56Rule 57Rule 58Rule 60Rule 62Rule 72Rule 73Rule 74Rule 76Rule 77Rule 78Rule 90Rule 94Rule 104Rule 105Rule 106Rule 108Rule 110Rule 122Rule 126Rule 128Rule 130Rule 132Rule 134Rule 136Rule 138Rule 140Rule 142Rule 146Rule 150Rule 152Rule 154Rule 156Rule 160Rule 162Rule 164Rule 168Rule 170Rule 172Rule 178Rule 184Rule 200Rule 204Rule 232 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=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.