I found Sipser's book and read that part (I, myself, was interested to find out the proof to that theorem). In the version of the book I found, in the step $4$, it is written that we replace the string on tape $3$ with the lexicographically next string.
So, if I understand it correctly, basically, at each step we start over with step $2$ (copying tape $1$ to tape $2$), than, on tape $3$, we take all possible strings (and by that, I mean all possible choices that the Non-Deterministic TM $N$ has).
The answer to the question "So why exactly in step $4$, do we replace the string on tape $3$ as opposed to appending?" : my guess is that it's easier to replace a string than to append it, because you would need to add in binary, but don't take my word for it.
Hope this helps you!
This type of machines is indeed equivalent in power to ordinary Turing machines. In fact, even if you remove the ability to perform the second type of moves (stay on the current cell), the power of the machine will not be affected. Here is how such a restricted TM can be converted to an unrestricted one.
When the machine needs to move the head to the right, it first puts a special mark, e.g. $\sim$, upon the current symbol. Then it goes all the way back to the leftmost cell, and starts moving rightward. While the machine does so, if another special mark, e.g. $\bullet$, is discovered on a symbol, it gets removed from it. Once the head encounters $\sim$, the machine replaces it with $\bullet$ and moves the head one cell to the right. This combination of moves is equivalent to one move to the right performed by an ordinary TM. Note that the symbol in the left adjacent cell is now marked with $\bullet$.
When the head needs moving to the left, there are three possibilities.
- The head points to the leftmost cell. In this case the tape contains no symbols marked with $\bullet$.
- The head points to the cell adjacent to the leftmost cell. In this case the tape does contain a symbol marked with $\bullet$, which is located in the leftmost cell.
- The head points to neither the leftmost cell nor its adjacent cell. In this case the tape also contains a symbol marked with $\bullet$, which is not in the leftmost cell. This is the symbol the head needs to move to.
The first case can be handled by marking the current symbol with $\sim$, moving the head to the leftmost cell and checking if the current symbol has $\sim$ upon it. If it does, remove it and remain in this cell, the move is now complete. Otherwise, check if the current symbol has $\bullet$ upon it. If it does, remove it, move the head to the adjacent cell, remove $\sim$ from the symbol in that cell and move to the leftmost cell again. This handles the second case. To deal with the last case perform the following steps.
- Mark the current symbol with $\bullet$.
- Move the head one cell to the right.
- Check if the current symbol is marked with $\bullet$.
- If it is, remove $\bullet$, move the head one cell to the right, remove $\sim$, move the head to the leftmost cell and scan the tape for an occurrence of $\bullet$. Once it is found, move the head one cell to the right and finish.
- Otherwise, put $\bullet$ upon it, move the head to the leftmost cell and scan the tape for the first occurrence of $\bullet$. Once it is found, remove it, move the head one cell to the right and proceed with step 2.
This simulates one move leftward performed by an ordinary TM. Note, that unless the head is pointing to the leftmost cell, the symbol in the left adjacent cell is marked with $\bullet$.
Best Answer
For any fixed $b$, we have $b < 2^k$ for some $k$ large enough, and $t(n) < 2^{t(n)}$ for $n$ large enough. So for $k,n$ large enough we have $$ t(n) b^{t(n)} \le 2^{t(n)} \left(2^k\right)^{t(n)} = 2^{t(n) + kt(n)} = 2^{O(t(n))}. $$