Verifying time complexity of Turing machines

•It is undecidable whether a multi-tape TM runs in time T(n)T(n)iffT(n)≥n+1T(n)≥n+1.•For T(n)=Ω(nlog⁡n)T(n)=Ω(nlog⁡n), T(n)≥n+1T(n)≥n+1, it is undecidable whether a one-tape TM runs in time T(n)T(n).•For nice T(n)=o(nlog⁡n)T(n)=o(nlog⁡n), it is decidable whether a one-tape TM runs in time T(n)T(n).

We show that, for all reasonable functions T(n)=o(nlog⁡n)T(n)=o(nlog⁡n), we can algorithmically verify whether a given one-tape Turing machine runs in time at most T(n)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)T(n)≥(n+1) and T(n)=Ω(nlog⁡n)T(n)=Ω(nlog⁡n), there exists no algorithm that would verify whether a given one-tape Turing machine runs in time at most T(n)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)T(n) iff T(n0)<(n0+1)T(n0)<(n0+1) for some n0∈Nn0∈N.We also prove a very general undecidability result stating that, for any class of functions FF that contains arbitrary large constants, we cannot verify whether a given Turing machine runs in time T(n)T(n) for some T∈FT∈F. This is an extension of the following folkloric results: we cannot verify whether a Turing machine runs in constant, linear or polynomial time.