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?



non-deterministic turing machines
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.*


