Difference between revisions of "Elementary cellular automaton"
From Wiki @ Karl Jones dot com
Karl Jones (Talk | contribs) (Created page with "In [[mathematics and [[computability theory]], an '''elementary cellular automaton''' is a one-dimensional cellular automaton where there are two possible states (labeled...") |
Karl Jones (Talk | contribs) |
||
| (One intermediate revision by the same user not shown) | |||
| Line 1: | Line 1: | ||
| − | 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. | + | 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]]. | As such it is one of the simplest possible models of [[computation]]. | ||
| Line 9: | Line 9: | ||
* [[Cellular automaton]] | * [[Cellular automaton]] | ||
* [[Computability theory]] | * [[Computability theory]] | ||
| + | * [[Computation]] | ||
* [[Mathematics]] | * [[Mathematics]] | ||
| + | * [[Rule 110]] | ||
| + | * [[Turing completeness]] | ||
== External links == | == External links == | ||
Latest revision as of 19:23, 23 September 2016
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
External links
- Elementary cellular automaton @ Wikipedia
