 |
When Stephen Wolfram surveyed the simplest one dimensional cellular automata and announced his four Classes, it seemed that there were none of the prized Class IV automata amongst the binary, first-neighbor automata. However, he thought that he saw possibilities in Rule 110, so much so that he dedicated Appendix 15 of his book [53] to some of its properties, including a collection of gliders. The rule attracted attention for other reasons, but little seems to have been done with it for a decade. Then, in the fall of 1998 at a meeting in Santa Fe, Matthew Cook is reported to have announced that the rule was computation universal.
There is little additional information concerning this announcement. Cook had maintained in Internet Web page dedicated to Rule 110, which was subsequently transferred to Hungary [88] and then retired. His presentation is scheduled for publication in the Proceedings of the CA98 meeting; further information may be available in Wolfram's forthcoming A New Science book.
There is some sporadic information of the Internet, with very little actually published in the literature. Li and Nordahl [91] were more interested interested in the long term state density in their 1992 paper, but Lindgren and Nordahl [92] were already concerned with the possibilities of universal computation in an article from 1990. They cautioned that one must be sure that it is the cellular automaton which is performing the computation, and that it is not the process by which its initial configuration is prepared which embodies the computation.