How can an arbitrary Turing machine running for $t$ steps be simulated in $O(n \log(n))$ steps?
I'm confused about a point regarding the Time Hierarchy Theorem. In order to establish the upper bound for this theorem it's necessary to show the following:
We're given $(\langle M \rangle, t)$ where $\langle M \rangle$ is the encoding of a Turing machine $M$ and $t$ is a natural number given in unary. Claim: one can tell whether $M(\langle M \rangle,t)$ accepts within $t$ steps using only $O(n \log(n))$ steps where $n$ is the size of $(\langle M \rangle, t)$.
I can buy that this is possible for any fixed $M$. But the claim also needs to hold if $t$ is fixed and $M$ varies. Or if either vary. At this point I'm getting a lot more skeptical. Here's <PERSON>'s proposed solution $D$:
We can think of $D$'s single tape as organized into tracks. One way to get two tracks is by storing one track in the odd positions and the other in the even positions. Alternatively, the two-track effect may be obtained by enlarging $D$'s tape alphabet to include each pair of symbols, one from the top track and the second from the bottom track. 143
We can get the effect of additional tracks similarly. Note that multiple tracks introduce only a constant factor overhead in time, provided that only a fixed number of tracks are used. Here, $D$ has three tracks.
One of the tracks contains the information on $M$'s tape, and a second contains its current state and a copy of $M$'s transition function. During the simulation, $D$ keeps the information on the second track near the current position of $M$'s head on the first track. Every time $M$'s head position moves, $D$ shifts all the information on the second track to keep it near the head. Because the size of the information on the second track depends only on $M$ and not on the length of the input to $M$, the shifting adds only a constant factor to the simulation time. Furthermore, because the required information is kept close together, the cost of looking up $M$'s next action in its transition function and updating its tape is only a constant.
(Emphasis mine)
The highlighted passages seem very suspect to me. These operations are only constant if $M$ is kept fixed. They are not constant if $M$ is allowed to vary. Is there a simple fix to this argument? 143