# basic turing machine

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?

• this belongs to computer science – Zonko Feb 14 '17 at 17:40
• @cloudchamber Are you using the Boolos and Jeffrey book? – 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".

• is mine wrong, then, or just inefficient? – cloudchamber Feb 14 '17 at 18:14
• It is incomplete. You didn't specify the halting state nor its rules. And yes, it is inefficient ;-) – 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.

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