How can we prove that every Turing machine $TM$ can be altered to a new Turing machine $TM'$ which can perform $2$ of $3$ operations in every step, how can we define this altered Turing machine.
$TM: \delta(Q \times \Gamma) \to Q \times \Gamma \times \{L,R\}$
$TM': \delta(Q \times \Gamma) \to (Q \times \Gamma) \cup (\Gamma \times \{L,R\}) \cup (Q \times \{L,R\})$
Operations :
move head ($L$ or $R$) and change a state, or write on tape and move head, or write on tape and change a state.
HINT
For each of the original state transitions, define some additional states that the new machine has, so that whenever the original machine goes through one transition, the new machine goes through several transitions that together emulate the original transition.
Example:
Original state transition: If you are in state $1$ and see a $0$, write a $1$, move right, and go to state $2$
Replace this with two new transitions:
If you are in state $1$ and see a $0$, write a $1$ and go to state $1a$.
If you are in state $1a$ and see a $1$, move right, and go to state $2$.
If you think about it, you find that this kind of thing can always be done, and in fact you see that you don't need the second of the three operations ... you can do it just using move+change state and write+change state. In fact, using these latter two you get what is known as the 'quadruple' formulation of Turing-machines.
