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?


1 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.