I'm trying to create a TM that changes all $a$'s to $b$'s and all $b$'s to $a$'s in a given string and then halts on the first blank space it encounters. What I have is:

$$ \langle q_1,a,b,q_1\rangle \\ \langle q_1,b,R,q_2\rangle \\ \langle q_2,a,L,q_1\rangle \\ \langle q_2,b,a,q_2\rangle $$

I'm new to Turing machines, so I'm wondering if it makes sense to convert $a$'s to $b$'s and then send $b$'s into a different state; is there a sort of temporal sequencing here that will send the $q_1$-manufactured $b$'s (former $a$'s) into $q_2$ as well? If so, how can you get around this problem to construct a suitable machine?

  • $\begingroup$ this belongs to computer science $\endgroup$ – Zonko Feb 14 '17 at 17:40
  • $\begingroup$ @cloudchamber Are you using the Boolos and Jeffrey book? $\endgroup$ – Bram28 Feb 14 '17 at 18:29

If you want just to exchange 'a' and 'b' symbols on the input string then you can just design a TM that always go rightward and changes the symbols on the fly:

\begin{align*} (q_1,a)\rightarrow(q_1,b,R)\\ (q_1,b)\rightarrow(q_1,a,R)\\ (q_1,\#)\rightarrow(q_2,\#,R) \end{align*}

Here $q_2$ is final and $\#$ is the blank symbol. $q_1$ is the initial state. $R$ means "move the head to the right".

  • $\begingroup$ is mine wrong, then, or just inefficient? $\endgroup$ – cloudchamber Feb 14 '17 at 18:14
  • $\begingroup$ It is incomplete. You didn't specify the halting state nor its rules. And yes, it is inefficient ;-) $\endgroup$ – Maczinga Feb 14 '17 at 18:17

I see that you are using the quadruple definition, rather than the more commonly used quintuple definition. But that is fine of course!

And yes, in many Turing-machine definitions you can have the machine halt without defining an explicit halting state; it just halts when there is not transition that applies.

Your machine will not work, however. If the input is $aa$ and the machine starts on the left $a$, then it will change the first $a$ to a $b$, and after that it will forever go back and forth between that $b$ and the $a$ to the right of it.

Try this instead:

$$ < q_1,a,b,q_2> \\ < q_1,b,a,q_2> \\ < q_2,a,R,q_1> \\ < q_2,b,R,q_1> \\ $$


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.