Universality in Elementary Cellular Automata
By Matthew Cook. Complex Systems, 2004
747 citations recorded by the source corpus.
The purpose of this paper is to prove a conjecture made by Stephen Wolfram in 1985, that an elementary one dimensional cellular automaton known as "Rule 110" is capable of universal computation. I developed this proof of his conjecture while assisting Stephen Wolfram on research for A New Kind of Science [1].
Subfields: Computational Theory and Mathematics
View Paper: https://www.semanticscholar.org/paper/12d6f0bb183050dd78b7671929455b7fdfdf73ce
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computational Theory and Mathematics
Citations in the corpus
- Complexity: A Guided Tour (2009, background): “In particular, the fact that an elementary one-dimensional CA with only two possible states is capable of universal computation [3] is especially revealing.”