Does Turing machine have no shift?
There are a lot of slightly different definitions of Turing machines out there! They usually differ in small but subtle ways. For example, some authors say that a Turing machine's head moves left or right, and writes the symbol; some authors say that it can also stay still. You have seen that Papadimitriou and Lewis allow either replacing the character on the tape, or moving left or right, which is slightly different than both replacing the character on the tape and moving left or right.

That sounds like bad news, but the good news is that you can prove that all of these different definitions are equivalent. Your textbook will have some exercises related to that. For example, we can prove:


That Turing Machines that can move left, right, or stay still are equivalent to ones that just move left or right.

Proof Idea: The Turing Machine that can only move left or right can "mimic" staying still by first moving one step to the right, then moving one step to the left. It takes $2$ steps instead of $1$, but it does the same thing.
That Turing Machines that move the head OR write a symbol are equivalent to those that move the head AND write a symbol at each step.

Proof Idea: the one that moves-or-writes can simulate the behavior of the one that moves-and-writes by first writing, then moving. So it takes $2$ steps instead of $1$, but it does the same thing. On the other hand, the one that moves-and-writes can simulate the behavior of the moves-or-writes one as follows: in order to move without writing, it should write the same symbol that is already on the tape (so that the write has no effect). And in order to write without moving, it should move left and then right, so that there is no net effect.