Notes

Chapter 11: The Notion of Computation

Section 12: Universality in Turing Machines and Other Systems


s=2, k=2 Turing machines

As illustrated on page 761, even extremely simple Turing machines can have behavior that depends in a somewhat complicated way on initial conditions. Thus, for example, with the rule

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

the head moves to the right whenever the initial condition consists of odd-length blocks of 1's separated by single 0's; otherwise it stays in a fixed region.

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