non-deterministic turing machines I have one simple question:
There is a set, which can be decided in polynomial time by a (one-band) non-deterministic Turing Machine.
Why should there exist one (one-band) non-deterministic Turing Machine, which decides the same set, but with the additional property: There exists one natural number k, such that all the possible calculations last exactly n^k steps, if the input has the length n?
This is one "without-loss-of-generality-assumption" in the proof of a theorem. (namely the proof of the Theorem of Fagin which says: "ESO captures NP")
I cannot understand it. How can we manipulate the first machine to get the second machine?
 A: 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.
