Matthew Cook proved that CA Rule 110 is capable of universal computation

Matthew Cook’s proof, developed while assisting Stephen Wolfram on A New Kind of Science and published in Complex Systems in 2004, resolved a conjecture Wolfram had posited in the 1980s. Cook proved that Rule 110, a seemingly simple one-dimensional cellular automaton, is capable of universal computation. This significant achievement confirmed that Rule 110 could simulate a Turing machine, thus performing any computation that a Turing machine is capable of. Cook’s proof not only validated Wolfram’s hypothesis but also underscored the profound computational possibilities inherent in cellular automata, enhancing their standing in computational theory and the study of complex systems. This all in turn led to the continued usage and interest in the creation of visual forms.