Verifying time complexity of Turing machines

We show that, for all reasonable functions T(n) = o(nlogn), we can algorithmically verify whether a given one-tape Turing machine runs in time at most T (n). This is a tight bound on the order of growth for the function T because we prove that, for T (n) >= (n + 1) and T(n) = Omega(nlogn), there exists no algorithm that would verify whether a given one-tape Turing machine runs in time at most T (n). As opposed to one-tape Turing machines, we show that we can verify whether a given multi-tape Turing machine runs in time at most T(n) iff T(n(0)) < (n(0) + 1) for some n(0) epsilon N. We also prove a very general undecidability result stating that, for any class of functions F that contains arbitrary large constants, we cannot verify whether a given Turing machine runs in time T(n) for some T epsilon F. This is an extension of the following folkloric results: we cannot verify whether a Turing machine runs in constant, linear or polynomial time. (C) 2015 Elsevier B.V. All rights reserved.