In the 1990's Matthew Cook served as a research assistant to Stephen Wolfram, where among other things he was directed to develop a proof showing that the Rule 110cellular automaton is Turing-complete. Under non-disclosure until the publication of Stephen Wolfram's A New Kind of Science, Cook nevertheless presented his proof at a Santa Fe Institute conference. Subsequently, it was stricken from the published proceedings by court order.
Rule 110 is an extremely simple system, and the fact that it is Turing-complete is remarkable.
