Notes

Chapter 12: The Principle of Computational Equivalence

Section 8: Undecidability and Intractability


[Turing] machine 1507

This machine shows in some ways the most complicated behavior of any s=2, k=2 Turing machine. As suggested by picture (k) it fails to halt if and only if its configuration at some step matches {0 ..., {1, 1}, 1, ___} (in the alternative form of page 888). For any input x one can test whether the machine will ever halt using

u[{Reverse[IntegerDigits[x, 2]], 0}] u[list_] := v[Split[Flatten[list]]] v[{a_, b_:{}, c_:{}, d_:{}, e_:{}, f_:{}, g___}] := Which[ a == {1} || First[a] == 0, True, c == {}, False, EvenQ[Length[b]], u[{a, 1 - b, c, d, e, f, g}], EvenQ[Length[c]], u[{a, 1 - b, c, 1, Rest[d], e, f, g, 0}], e == {} || Length[d] >= Length[b] + Length[a] - 2, True, EvenQ[Length[e]], u[{a, b , c, d, f, g}], True, u[{a, 1 - b, c, 1 - d, e, 1, Rest[f], g, 0}]]

This test takes at most n/3 recursive steps, even though the original machine can take of order n^2 steps to halt. Among s=3, k=2 machines there are 314 machines that do the same computation as 1507, but none any faster.


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