Verifying Time Complexity of Turing Machines - Gajser, David (Informatica, 2016)
This paper presents a summary of the doctoral dissertation of the author, which analyzes in detail the following problem. For a function T that maps non-negative integers to non-negative reals, how hard is it to verify whether a given Turing machine runs in time at most T(n)? Is it even possible?