W110
- This article is not detailed enough and needs to be expanded. Please help us by adding some more information.
W110, also known as Rule 110, is a one-dimensional cellular automaton notable for its Turing-completeness. It it named after its wikipedia:Wolfram code.
Computational class
In 1985, Rule 110 was conjectured to be Turing-complete. Around 1998, wikipedia:Matthew Cook proved it. Cook was sued by their employer in 2000 for attempting to publish, but the lawsuit was terminated and eventually they were able to show the following result:
Theorem (Turing-completeness). Under certain initial conditions, rule 110 simulates a glider system where it is undecidable whether a given glider will appear. (Cook, 2004)
Cook also proved a less esoteric result:
Theorem. Under certain initial conditions, rule 110 simulates a cyclic tag system. (Cook, 2004)
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.
External links
There are articles about Rule 110 on other wikis:
References
- Wolfram Research Inc. v. Cook, filed in 2000 in District Court in the Central District of California
- "Universality in Elementary Cellular Automata", Cook 2004