Notes

Chapter 11: The Notion of Computation

Section 12: Universality in Turing Machines and Other Systems


[Universality for] classes of systems

This chapter has shown that various individual systems with fixed rules exhibit universality when suitable initial conditions are chosen. One can also consider whole classes of systems in which rules as well as initial conditions can be chosen. And then one can say for example that as a class of systems cellular automata are universal, but neighbor-independent substitution systems are not.


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