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.)


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