Time Complexity of Universal Turing Machine Simulations and the Time Hierarchy Theorem

Question

I have a little problem to understand the proof of the Time Hierarchy Theorem (Hennie and Stearns, 1966) that ensures the existence of a language acceptable in $U(n)$ but not acceptable in $T(n)$ for any functions $T(n),U(n)$, such that $U(n)$ is time-constructible and

$$n \leq T(n) = o\left(\frac{U(n)}{\log T(n)}\right).$$

This proof is based on the existence of the Universal Turing machine simulating any Turing machine with time complexity $T(n)$ in time $T(n) \log T(n)$.

I understand (and believe) the proof that every $k$-tape Turing machine can be simulated by a two-tape Turing machine with a logarithmic overhead. However, I understand this construction only if the simulated Turing machine is fixed, not in the case of the Universal TM simulation.

I see one "problem" in the reasoning given in the cited paper (and also in several standard books on computational complexity) related to the construction of the Universal machine. This "problem" is that in the Universal machine simulation, one computational step of a simulated machine is supposed to be executed in constant time by the Universal machine. In other words, the length of the description of the simulated machine is supposed to be constant.

But is this OK? Since in the proof of the Time Hierarchy Theorem, the input given to the simulated Turing machine is exactly this description, and thus, the description is somehow dependent of $n$. I am aware of that the description can be lengthened by a sequence of leading bits, but this does not seem to solve this problem.

That is, I cannot figure out why the computation step of a simulated machine can be supposed to be executed in a constant time by the Universal machine. The paper of Hennie and Stearns does not pay much attention to this, it merely states that this time is something that is implicitly assumed to be a constant. Similarly in the textbooks I have read on the topic.

I simply cannot figure out why the time complexity of the simulation is $T(n)\log T(n)$, and not $n T(n) \log T(n)$.

I am almost sure that I am missing something. However, I am trying to understand this for a relatively long time and somehow I cannot figure this out.

Answer 1

I'm referring here to the proof of the hierarchy theorem as I am familiar with it, in which I don't see the problem you mention.

We define the language $L=\{(M,w): M $ does not accept $(M,w)$ within $\le \frac{t(n)}{|M|^3+|M|\log t(n)}, n=|(M,w)|\}$ (where $t$ is the time function we are working on).

We show that $L$ is decidable in $O(t(n))$ using the universal machine, and in the universal machine each step is indeed dependent on the size of the machine, which is why we have $|M|^3$ in the denominator (the 3 is just some upper bound on the computations needed to simulate a step).

For completeness of the answer: when we try to reach a contradiction, then we assume that there exists a machine $T$ that decides $L$. After this assumption, the encoding of $T$ is fixed, and then a simulation of a single step really does take constant time, and we can reach a contradiction by taking a long enough $w$ to increase the length of the input without changing $T$.