Notes

Chapter 11: The Notion of Computation

Section 12: Universality in Turing Machines and Other Systems


[Turing] machine 596440

For any list of initial colors init, it turns out that successive rows in the first t steps of the compressed evolution pattern turn out to be given by

NestList[Join[{0}, Mod[1 + Rest[FoldList[Plus, 0, #]], 2], {{0}, {1, 1, 0}}Mod[Apply[Plus, #], 2] + 1] &, init, t]

Inside the right-hand part of this pattern the cell values can then be obtained from an upside-down version of the rule 60 additive cellular automaton, and starting from a sequence of 1's the picture below shows that a typical rule 60 nested pattern can be produced, at least in a limited region.

The presence of glitches on the right-hand edge of the whole pattern means, however, that overall there is nothing as simple as nested behavior—making it conceivable that (possibly with analogies to tag systems) behavior complex enough to support universality can occur. The plot below shows the distances between successive outward glitches on the right-hand side; considerable complexity is evident.

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