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) which is capable of universal computation (see Turing completeness).

See also

• Cellular automaton
• Computability theory
• Computation
• Mathematics
• Rule 110
• Turing completeness

External links

• Elementary cellular automaton @ Wikipedia