W110
Jump to navigation
Jump to search
- This article is not detailed enough and needs to be expanded. Please help us by adding some more information.
W110 (or Wolfram's rule 110) is a 1D Cellular automaton proven to be Turing-complete. Its name is derived from how each cell's state is determined.
Computational class
W110 has been proven to be Turing-complete as it can implement a cyclic tag system. (Note that this requires the use of an infinite pattern of cells, with two different infinitely-repeating patterns extending to the left and right – the behaviour is not known to be Turing-complete starting from a finitely initialized pattern.)