Notes

Chapter 12: The Principle of Computational Equivalence

Section 8: Undecidability and Intractability


Growth rates [of halting times]

Some Turing machine can always be found that has halting times that grow at any specified rate. (See page 103 for a symbolic system with halting times that grow like Nest[2^#&, 0, n].) As discussed on page 1162, if the growth rate is too high then it may not be possible to prove that the machines halt using, say, the standard axioms of arithmetic. The maximum halting times above increase faster than the halting times for any specific Turing machine, and are therefore ultimately not computable by any single Turing machine.


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