For any function T, consider the following decision problem HALTT: does a given Turing machine M run in time at most T(n)? More generally, if F is a set of functions, then HALTT is the problem of deciding if M runs in time at most T(n) for some T ∈ F. The question arises under which conditions these problems are decidable. As may be expected, the answer is negative in most cases, but some exceptions occur when T grows slowly or F contains only slowly growing functions.
For multitape Turing machines, this paper shows mainly negative results: HALTT is decidable only if T(n0) ≤ n0 for some , and HALTF is undecidable whenever F contains arbitrarily large constant functions.
More interesting results are obtained for the case where M is restricted to one-tape Turing machines, which gives rise to corresponding decision problems and . On the one hand, is undecidable if T(n)≥ n+1 and T(n)=Ω(n log n). On the other hand, is decidable whenever T=o(n log n) and T is sufficiently “well-behaved”; the latter condition is of course defined precisely. This is the main result and definitively the most intricate one in the paper. The following corollary is obtained: a one-tape Turing machine that runs in time o(n log n) actually runs in linear time. This fact is new, although it has long been known that one-tape Turing machines with linear time complexity are capable of accepting the same class of languages as one-tape Turing machines with time complexity o(n log n), namely the class of regular languages.
For the sake of simplicity, the proofs are worked out only for deterministic Turing machines, but it is noted in the final section that they extend to nondeterministic ones as well.
