Prove the equivalence of the modified Turing Machines and the standard Turing Machines

Question

We have a Turing Machine that cannot write the same symbol it has read in a transition, meaning it should always alter the symbol when passing it. How can we prove that such machines have equal processing power compared with the standard Turing Machines?

Answer 1

Since a modified Turing machine is a special kind of the standard Turing machine, the power of modified Turing machines is at most that of standard Turing machines.

Now suppose $S$ is a stand Turing machine with $\Gamma$ as its alphabet on tape.

Let $\Gamma'$ be a copy of $\Gamma$, i.e., for all $\gamma\in\Gamma$, there is a corresponding $\gamma'\in\Gamma'$.

Let Turing machine $M$ be the same as $S$ except that

• $M$'s alphabet on tape is $\Gamma\sqcup\Gamma'$.
• Suppose $M$ read $\alpha\in\Gamma$ or $\alpha'\in \Gamma'$. Then $M$ will behave like $S$ as if $S$ had read $\alpha$, except that $M$ will write $\beta'$ instead if $S$ would write $\beta\in\Gamma$ when $\alpha$ was read.

We see that $M$ is a modified Turing machine that simulates $S$. Hence the power of modified Turing machines is at least that of standard Turing machines.