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.



Image Source Notebooks:

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