Notes

Chapter 11: The Notion of Computation

Section 12: Universality in Turing Machines and Other Systems


Rule 60 Turing machines

One can emulate rule 60 using the 8-case s = 3, k = 3 Turing machine (with initial condition Append[list + 1, 1] surrounded by 0's)

{{1, 2} {2, 2, 1}, {1, 1} {1, 1, 1}, {1, 0} {3, 1, -1}, {2, 2} {2,1, 1}, {2, 1} {1, 2, 1}, {3, 2} {3, 2, -1}, {3, 1} {3, 1, -1}, {3, 0} {1, 0, 1}}

or by using the 6-case s = 2, k = 4 Turing machine (with initial condition Append[3list, 0] with 0's on the left and 1's on the right)

{{1, 3} {2, 2, 1}, {1, 2} {1, 3, -1}, {1, 1} {1, 0, -1}, {1, 0} {1, 1, 1}, {2, 3} {2, 1, 1}, {2, 0} {1, 2, 1}}

This second Turing machine is directly analogous to the one for rule 110 on page 707. Random searches suggest that among s = 3, k = 3 Turing machines roughly one in 25 million reproduce rule 60 in the same way as the machines discussed here. (See also page 665.)



Image Source Notebooks:

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