I'm currently reading Computational Complexity: A Modern Approach. In this book, they give a proof of a universal Turing machine $U$ such that if $M(x)$ runs in $T$ steps, then $U(\lfloor M \rfloor, x)$ runs in $CT \log T$ steps where $C$ depends only on $M$'s alphabet size, number of tapes, and number of states. I'll describe $U$ loosely here:
It has an input tape, output tape, tape for $M$'s states and transition functions, tape for $M$'s current state, and one work tape. We say $M$ has $k$ work tapes and an alphabet of $\Gamma$.
$U$ uses an alphabet of $\Gamma^k$ to put the letters of all $k$ tapes on one cell and has a clever way of imitating the left and right shifts of different heads.
Since we only have $T$ steps, we only need to go from $-T$ to $T$. We'll say $L_i$ goes from $2^i$ to $2^{i+1}-1$ and $R_i$ goes from $-2^{i+1}+1$ to $-2^i$. This goes from $i=0$ to $i=\log T+1$. For any $i$, $L_i$ and $R_i$ is full of blank symbols, half-blank half-filled, or completely filled. Furthermore, the total number of blank symbols in both $L_i$ and $R_i$ at one time is $2^i$, meaning half of all of the cells are blank while the other half is information.
To left shift, find the smallest $i$ so $R_i$ is not empty and thus $L_i$ is not full. Put the leftmost non-blank symbol in position $0$ (i.e. under the head in $M$) and move the other $2^{i-1}-1$ non-blank symbols into the empty $R_0,R_1,...R_{i-1}$. This leaves all of those zones half-empty.
Push the $2^{i-1}$ leftmost non-blank symbols in $L_{i-1},...,L_1$ into $L_i$ and then reorganize the other non-blank symbols to make $L_{i-1},...,L_1$ all half-full.
Right shifts look similarly, except switch the roles of the left and right zones.
I want to solve the following exercise:
Define a TM $M$ to be oblivious if its head movement does not depend on the input but only on the input length. That is, M is oblivious if for every input $x \in \{0, 1\}^∗$ and $i \in N$, the location of each of $M$’s heads at step $i$ of execution on input $x$ is only a function of $\lvert x \rvert$ and $i$. Show that for any time-constructible $T : \Bbb{N} \rightarrow \Bbb{N}$, if $L \in \mathbf{DTIME}(T(n))$, then there is an oblivious TM that decides $L$ in $O(T(n)\log T(n))$ time.
Hint: Show that $U$ can be tweaked to be oblivious.
Now, my question is, under such a machine, while maintaining $CT\log T$ time, how do we make $U$ oblivious? I see how putting the input down initially and the left/right shifts are simply functions of $\lvert x \rvert$, but when we decide to left/right shift each tape has to decide on $x$ since we're not given that $T$ is oblivious, so how do we time the left and right shifts of $U$ so that they only depend on $\lvert x \rvert$ and not on the actual content of $x$?
