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 2n + 2 - 3, achieved for x = 2n - 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.



Image Source Notebooks:

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