Notes

Chapter 11: The Notion of Computation

Section 12: Universality in Turing Machines and Other Systems


[Universal] tag systems

Marvin Minsky showed in 1961 that one-element-dependence tag systems (see page 670) can be universal. Hao Wang in 1963 constructed an example that deletes just 2 elements at each step and adds at most 3 elements—but has a large number of colors. I suspect that universal examples with blocks of the same size exist with just 3 colors.

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