Universality in Elementary Cellular Automata
Matthew Cook
Department of Computation and Neural Systems,
Caltech, Mail Stop 136-93,
Pasadena, California 91125, USA
Abstract
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].
