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...
Asked By : CodyBugstein
Answered By : babou
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.
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/43766 Ask a Question Download Related Notes/Documents