# Construction of a Turing machine

I am looking at the following:

Costruct a composite turing machine, that reverses the words $w_1$ and $w_2$ over the alphabet $\{\_, x_2, \ldots , x_m\}$ as follows: $$\ldots \_ w_1\_ w_2\underline{\_} \ldots \mapsto \ldots \_ w_2^R\_ w_1\underline{\_} \ldots$$ The first symbol of $w_2^R$ is on the position where the first symbol of $w_1$ was at the beginning.

The suggested solution is the following: We have to define the TM that reverses an arbitrary non-empty string of the alphabet: $$\ldots \_ w \underline{\_}\ldots \rightarrow \ldots \_ w^R \underline{\_}\ldots$$ This can we done as follows:

This TM does the same as the one that copies a string, but this reverses the word and shifts the reversed copy to the original word.

We get the following TM:

If none of the words is empty, the TM reverses $w_2$ and copies $w_1$ at the position on the right of $w_2^R$. Now $w_1$ must be deleted. To do that we connect $w_2^R$ and $w_1$ by $z$, that is not in the alphabet, to one word. We shift that word on $w_1$ and delete $z$. The TM halts on the right of $w_1$.



I haven't really understood the definition of the reversing TM (the first picture). Could you explain it to me?

We have that $R$ is the TM that goes to the right till it reads a blank. $L$ is the TM that goes to the left till it reads a blank. $V$ is the TM that translates.

The function of TM is the following:

First the word $w_2$ is reversed. Then the TM copies the word $w_1$ on the right of $w_2^R$. So, on the tape we have now $w_1\_w_2^R\_w_1$. We have to shift $w_2^R\_w_1$ to the left, by overwriting it on the first $w_1$, right? To shift $w_2^R\_w_1$ we have to connect that to one word, so we replace the blank by a symbol $z$ that is not in the alphabet. After having shifted the new word we delete again the symbol $z$. Have I understood it correctly?

• 1st, are you familiar with the defn of a TM, and understand the basic principles? hint for this problem, try simulating the rules by hand on a sample/ test input to see how they work. – vzn Jul 24 '17 at 20:39
• We define a TM by showing the transition function, or not? Suppose we have the word $w=\_x_2x_2x_4x_3$. So, on the tape we have $\ldots \_x_2x_2x_4x_3 \_\ldots$ and the head shows at the blank at the right to the word, or not? So, $\ldots \_x_2x_2x_4x_3 \underline{\_}\ldots$. Then do we go one position to the left? If yes, then we have $\ldots \_x_2x_2x_4\underline{x_2} \_\ldots$. From the transition function, since the head reads a $x_2$, we have to apply $bR^2x_2L^2x_2$. What exactly does this mean? @vzn – Mary Star Jul 24 '17 at 22:14
• Having on the tape $\ldots \_x_2x_2x_4\underline{x_2} \_\ldots$ we apply $bR^2x_2L^2x_2$. That means that we mark the letter $x_2$ by $b$ go to the second blank on the right right there $x_2$ go back to the second blank on the left (so the position we were) and write again $x_2$, and so we get at this step $\ldots \_x_2x_2x_4\underline{x_2} \_ x_2\ldots$, right? I haven't understood if the Tm reads the blank, what does $R^2V \rightarrow \text{HALT}$ means? That we go at the second blank on the right and then we translate the head the beginning and halts? @vzn – Mary Star Jul 25 '17 at 1:35