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

  • 3
    $\begingroup$ There are a fixed, finite number of options for what character is in each tape cell. That means you can use the state of the machine to remmeber what was in a cell (or, more generally, in any fixed, constant number of cells). $\endgroup$ – David Richerby Jun 19 '15 at 22:59
  • $\begingroup$ @babou yes because I forgot. Thanks for your help! $\endgroup$ – CodyBugstein Jul 5 '15 at 4:46

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.

  • $\begingroup$ Can you explain the syntax you used? I'm used to $a → b, L$ meaning if you are on $a$, change it to $b$ and move left. You added some $q$s in there and I don't understand $\endgroup$ – CodyBugstein Jun 19 '15 at 23:06
  • $\begingroup$ You use a simplified syntac because it decorates arrows between states in a diagram. Since there is no diagram, I am only making the states explicit, the from state and the to state. $\endgroup$ – babou Jun 19 '15 at 23:13

To this end, you first need to find the middle point. In this answer there is a good algorithms to do that:

  1. mark the start and the end of your tape
  2. move the start marker one step to the right, move the end marker one step to the left
  3. repeat until the markers reach each other

Then, you move the "a" until you get to the marker, and remove the marker.


How to move a letter: Say you have an "a" among a string of 0 and 1. here is a way to shift it to the right:

  1. $q_{start},a \to q_?,a,L\quad$ and also $\quad q_{?},a \to q_?,a,L$
  2. $q_?,0 \to q_0,a,R$
  3. $q_?,1 \to q_1,a,R$
  4. $q_0,* \to q_?,0,L$
  5. $q_1,* \to q_?,1,L$

where $*$ is "don't care".

What is going on here? If we see an $a$, we move to the cell to the right of it, remember what was written there, and write an $a$ instead. If it was a $0$ we deleted, we move to state $q_0$, if it was a $1$ we move to $q_1$. This is how we "remember" what was deleted. Then we move the head one step to the left, and write 0 or 1 according to whether we are in state $q_0$ or $q_1$. Then we move one step to the right and repeat the same process. Try to simulate it for yourself on a paper...

  • $\begingroup$ The problem is, how do I move a marker? I can only change the tape slot that I am on. I can't change something in the next box $\endgroup$ – CodyBugstein Jun 19 '15 at 22:50
  • $\begingroup$ I get you, let me edit the answer. $\endgroup$ – Ran G. Jun 19 '15 at 22:53

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.