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:

enter image description here

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:

enter image description here

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?

  • 1
    $\begingroup$ 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. $\endgroup$ – vzn Jul 24 '17 at 20:39
  • $\begingroup$ 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 $\endgroup$ – Mary Star Jul 24 '17 at 22:14
  • $\begingroup$ 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 $\endgroup$ – Mary Star Jul 25 '17 at 1:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.