This is possible, but it is somewhat tricky to do. Here is an outline of one way to do it... Start with your original one-tape Turing machine $M_0$ which runs in time $\leq k + n^k$ (say) on input of length $n$. First create a two-tape Turing machine $M_1$ which simulates $M_0$ on one tape and keeps track of a step-counter on the other tape. The counter is initially set to value $k + n^k$ and is decremented at each simulation step. When the simulation of $M_0$ terminates, $M_1$ keeps doing dummy moves until the counter is exhausted. Thus $M_1$ runs in exactly the same time on every input of length $n$. Finally, we simulate $M_1$ on a one-tape Turing machine $M_2$ as follows. Think of even cells as belonging to the first tape of $M_1$ and odd cells as belonging to the second tape of $M_1$. To keep track of where the two $M_1$ heads, each symbol will now have a plain and a red variant; there will be only two red variants at any given time and they will mark the two head positions. It is straightforward to simulate $M_1$ on such a tape, but the simpler ways do not simulate each step of $M_1$ in a constant number of steps since switching from one head to the other requires a variable number of moves. To remedy this, first note that $M_1$ never uses more than $\ell + n^\ell$ cells of the tape for some $\ell$ that can be effectively estimated from $k$ and the above transformations. When it starts, $M_2$ reads the input length and places freshly minted markers on the $(\ell + n^\ell)$-th cell, well beyond any cell required to simulate $M_1$. Whenever $M_2$ simulates a step of $M_1$, it proceeds as follows: * Starting at the base of the tape, $M_2$ finds the appropriate tape head (red symbol in even/odd position). * $M_2$ then performs the appropriate action, these each take a fixed finite amount of steps which may vary from operation to operation. Once the operation is completed, $M_2$ dances around a little so that it returns to the original tape position exactly 1001 steps after it arrived there. * Then $M_2$ moves right until it finds the marker at position $\ell + n^\ell$ at which point it turns around and returns to the base of the tape. Although this is very inefficient, $M_2$ does correctly simulate $M_1$ and it takes exactly the same amount of time to simulate each step of $M_1$. Furthermore, $M_2$ still runs in polynomial time, though the polynomial is much worse than the original $k + n^k$. **Edit:** *This answer was simplified from its original version.*