Notes

Chapter 11: The Notion of Computation

Section 11: The Threshold of Universality in Cellular Automata


Claims of non-universality [in cellular automata]

Over the years, there have been a few erroneous claims of proofs that universality is impossible in particular kinds of simple cellular automata. The basic mistake is usually to make the implicit assumption that computation must be done in some rather specific way—that does not happen to be consistent with the way we have for example seen that it can be done in rule 110.


From Stephen Wolfram: A New Kind of Science [citation]