Cheap and Secure Web Hosting Provider : See Now

[Solved]: How do you swap consecutive boxes on a Turing Machine tape?

, ,
Problem Detail:

I can't figure out how to swap boxes on a Turing Machine tape.

So for example, I have a tape that says

a 1 0 1 1 1 0 ^ 

And I want to move that a over so that it is in the middle. (but my end goal is not important here)

How do I get the Turing Machine to do

1 a 0 1 1 1 0   ^  1 0 a 1 1 1 0     ^  etc... 

Here is a possible set of transition to do one move, as you request. Note that $x$ is to be replaced by $0$ and by $1$, so that each transition with $x$ is actually a pattern to be replaced by 2 transitions, one with $0$ and the other with $1$, instead of $x$ (so you really have 5 transitions below)
And of course $q_{2,x}$ stands for two states: $q_{2,0}$ and $q_{2,1}$.

I present things that way so that you know what to do if you can have more than two disctinct symbols to deal with.

The $*$ is just a wild card, indicating that the content of the tape does not matter.

This will do the required exchange, with $0$ or $1$. You end up in state $q_2$, still pointing to the $a$

\begin{align} q_1, a&\to q_{1,a},a,R\\ q_{1,a},x&\to q_{2,x},a,L\\ q_{2,x},*&\to q_2,x,R \end{align}

I hope this is clear.

What it does is to note $a$ in the finite state control, by going in state $q_{1,a}$, and then moving Right. There it notes in the finite state control whatever $x$ is found there, a $0$ or a $1$, thus going in state $q_{2,x}$, and write down the $a$ (so it can forget it), and moves back Left. Back on the left square, there is still an $a$, it does not matter, it can write down the $x$ it memorized in the finite state control, and move Right again, in state $q_2$, so that it is pointing to the $a$ that was moved.

Note that the $*$ could be replaced by $a$. The $*$ is a convenient notation to say that it does not matter, as you could have several symbols other than $a$ to be moved in this way.

$q_2$ is whatever state you need to be in after performing one such permutation.