Return to Answer

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.

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$ uses less 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 $n$ and places a freshly minted marker on the $(\ell + n^\ell)$-th cell, 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 to simulate $M_1$, these each take a fixed finite amount of steps which may vary from operation to operation. Once this 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.

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$ but 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 blue 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 sets up some freshly colored markers at fixed positions around 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, it finds the appropriate tape head (red symbol in even/odd position).

• It then performs the appropriate action, these each take a fixed finite amount of steps which may vary from operation to operation.

• Then it moves right until it finds the colored marker corresponding to the operation just performed, these are placed around position $\ell + n^\ell$ but they are slightly offset from each other to compensate for the exact amount of simulation steps needed to perform the operation as described in the previous bullet.

• Finally, it moves back from the colored marker to the base of the tape, where it awaits the next instruction.

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$ runs in polynomial time, though the polynomial is much worse than the original $k + n^k$.

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.

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_1$ which runs in time $\leq k + n^k$ (say) on input of length $n$.

First create a two-tape Turing machine $M_2$ which simulates $M_1$ but 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_1$ terminates, $M_2$ keeps doing dummy moves until the counter is exhausted. Thus $M_2$ runs in exactly the same time on every input of length $n$.

Finally, we simulate $M_2$ on a one-tape Turing machine 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 blue 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 sets up some freshly colored markers at fixed positions around 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, it finds the appropriate tape head (red symbol in even/odd position).

• It then performs the appropriate action, these each take a fixed finite amount of steps which may vary from operation to operation.

• Then it moves right until it finds the colored marker corresponding to the operation just performed, these are placed around position $\ell + n^\ell$ but they are slightly offset from each other to compensate for the exact amount of simulation steps needed to perform the operation as described in the previous bullet.

• Finally, it moves back from the colored marker to the base of the tape, where it awaits the next instruction.

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$ runs in polynomial time, though the polynomial is much worse than the original $k + n^k$.

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$ but 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 blue 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 sets up some freshly colored markers at fixed positions around 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, it finds the appropriate tape head (red symbol in even/odd position).

• It then performs the appropriate action, these each take a fixed finite amount of steps which may vary from operation to operation.

• Then it moves right until it finds the colored marker corresponding to the operation just performed, these are placed around position $\ell + n^\ell$ but they are slightly offset from each other to compensate for the exact amount of simulation steps needed to perform the operation as described in the previous bullet.

• Finally, it moves back from the colored marker to the base of the tape, where it awaits the next instruction.

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$ runs in polynomial time, though the polynomial is much worse than the original $k + n^k$.