Notes

Chapter 12: The Principle of Computational Equivalence

Section 8: Undecidability and Intractability


Longest halting times [in Turing machines]

The pictures below show the largest numbers of steps t[x] that it takes any machine of a particular type to halt when given successive inputs x. For s=2, k=2 the largest results for all inputs of sizes 0 to 4 are {7, 17, 31, 49, 71}, all obtained with machine 1447. For n>4 the largest results are 2^(n+2)-3, achieved for x = 2^n - 1 with machines 378 and 1351. For s=3, k=2 the largest results for successive sizes are {25, 53, 159, 179, 1021, 5419} (often achieved by machine 600720; see below) and for s=2, k=3 {35,83,843,8335} (often achieved by machine 840971). Note the similarity to the busy beaver problem discussed on page 889.


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