237
edits
→Cellular Automata, Game of Life and Universal Computation
| Line 81: | Line 81: | ||
Paul Rendell has implemented a Universal Turing Machine in Conway’s game of Life in 2010. The upper picture shows the pattern of it. | Paul Rendell has implemented a Universal Turing Machine in Conway’s game of Life in 2010. The upper picture shows the pattern of it. | ||
====Rule 110 Cellular Automaton==== | |||
The Rule 110 cellular automaton (often simply Rule 110) is an elementary cellular automaton with interesting behavior on the boundary between stability and chaos. In this respect it is similar to Conway's Game of Life. Also like Life, Rule 110 is known to be Turing complete. This implies that, in principle, any calculation or computer program can be simulated using this automaton. | |||
A computational system that can compute every Turing-computable function is called Turing complete (or Turing powerful). Alternatively, such a system is one that can simulate a universal Turing machine. | |||
In an elementary cellular automaton, a one-dimensional pattern of 0s and 1s evolves according to a simple set of rules. Whether a point in the pattern will be 0 or 1 in the new generation depends on its current value, as well as on those of its two neighbors. The Rule 110 automaton has the following set of rules: | |||