So, I have been given a TM where the head can access and write both the character that the head is pointing at and the next character to the right.

So if we have a TM abbb and the head is pointing at a, it can access and write into the the next character also ie the first b. So it has access to both the first and second characters of the string abbb. How would I show that this isn't actually a special TM but can be done with a regular TM too?


You want to show that this modified Turing machine is equivalent to the standard definition of a Turing machine, that is for every modified Turing machine $T'$ there exists a standard Turing machine $T$ such that $L(T')=L(T)$, and vice versa.

It is easy to show that for every standard Turing machine $T$ there is a modified Turing machine which accepts $L(T)$, just don't use the modified machine's ability to read or write to the input to the right of its head. Then these modified Turing machines are at least as powerful as standard Turing machines.

Now if $T'$ is a modified Turing machine which can read and write to the character immediately to the right of its head, we want to show that there exists a Turing machine $T$ which recognizes the same language as $T'$. Formally this gets a bit messy but the idea is whenever $T'$ would read or write an input from the cell to its right we add a sequence of states and transitions in which $T$ will move back and forth between the cell it is currently over in $T'$ and the cell to its right in $T'$ reading and writing as $T'$ does, then $T$ will move to the position and state specified in the transition function of $T'$. Essentially, if $T'$ reads from the cell to its right, $T$ will move to the right, read the input then move to the left. If $T'$ will would to the cell to its right, $T$ will move to the right, write the same thing $T'$ would have written, then move back, and transition to the same state $T'$ would have transitioned to.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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