Notes

Chapter 11: The Notion of Computation

Section 12: Universality in Turing Machines and Other Systems


Rule 110 Turing machines

Given an initial condition for rule 110, the initial condition for the Turing machine shown here is obtained as Prepend[4 list, 0] with 1's on the left and 0's on the right. The Turing machine

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

with s=4 states and k=3 possible colors also emulates rule 110 when started from Prepend[list+1, 1] surrounded by 0's. The s=3, k=4 Turing machine

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

started from Append[list, 0] with 0's on the left and 2's on the right generates a shifted version of rule 110. Note that this Turing machine requires only 8 out of the 12 possible cases in its rules to be specified.

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