I am having trouble understanding a mapping reduction and I would appreciate your help. Define

$\quad \begin{align} A_{TM} &= \{ \langle M, w \rangle \mid M \text{ Turing machine}, w \in \mathcal{L}(M)\} \\ S_{TM} &= \{ \langle M,w \rangle \mid M \text{ Turing machine}, w \in \mathcal{L}(M) \implies w^R \in \mathcal{L}(M)\} \\ \end{align}$

and consider the reduction of $A_{TM}$ to $S_{TM}$ as follows.

Given $\langle M, w \rangle$ the following Turing machine $M'$ is defined:

M' on input x:  
  if x = 01 then accept  
  else run M on w and accept x if M accepts w

I don't understand the reduction entirely, this reduction is supposed to solve $S_{TM}$ using $A_{TM}$. Why do I need to check if x = 01? There is no need to check anything about the reverse of $w$? How is that covered by the reduction?

  • $\begingroup$ Observe that $S_{TM}$ accepts $w$ if and only if it accepts $w^R$. $\endgroup$ – Pål GD Feb 11 '13 at 16:25
  • $\begingroup$ can you explain further? I'm not getting the hierarchy here, M gets a w, if M accepts it, why should M' get x? x is not the reverse of w. $\endgroup$ – user6821 Feb 11 '13 at 16:45
  • $\begingroup$ Just a typo: if the reduction is from $A_{TM}$ to $S_{TM}$ then it "is supposed to solve $A_{TM}$ using $S_{TM}$". $\endgroup$ – Vor Feb 11 '13 at 16:58
  • $\begingroup$ Do you understand what $S_{TM}$ is? That it accepts a machine if and only if that machine halts on $w$ if and only if it halts on $w^R$? Furthermore, as Vor says, you are to prove that $A \leq_m S$, i.e. that you can solve $A$ by using $S$. $\endgroup$ – Pål GD Feb 11 '13 at 17:11
  • $\begingroup$ What is $A_{TM}$? Where did you get this from? $\endgroup$ – Raphael Feb 11 '13 at 17:35

The idea of the reduction you give in your question is the following:

I) If $\langle M,w\rangle \in A_{tm}$, then $L(M')=\Sigma^*$.
II) If $\langle M,w\rangle \notin A_{tm}$, then $L(M')=\{10\}$.

thus, for any $w$, $\langle M,w\rangle \in A_{tm}$ iff $\langle M',w\rangle \in S_{tm}$.
In case (I), for any $w\in L(M')$ also $w^R\in L(M')$ hence $\langle M',w \rangle S_{TM}$ for any $w$. For case (II), there is no $w\in L(M')$ such that $w^R\in L(M')$ as well, thus for any $w$, $\langle M',w \rangle S_{TM}$.

Now for your question about accepting "10" no matter what: Assume we avoid this step. Then, in case (II), $L(M')=\emptyset$, hence $\langle M',w\rangle \in S_{tm}$ for any $w$, since the condition on $w,w^R$ vacuously holds. Now the mapping cannot map inputs $\langle M,w\rangle \notin A_{tm}$ to inputs outside $S_{TM}$ (since none exists).

The value "10" is arbitrary. Any other non-palindromic string will do.

| cite | improve this answer | |

Here's a possible reduction for $A_{tm} \le S_{tm}$.

Map input $\langle M,w\rangle$ to $\langle M', 0w1\rangle$ such that

$M'$ on input $x$:
0. if $x$ can be written as $1x'0$ for some $x'$, accept. Otherwise,
1. if $x$ can be written as $0x'1$ for some $x'$, run $M$ on $x'$ and output the same.
2. Otherwise, accept (or reject, it doesn't matter).

If $\langle M,w\rangle \in A_{TM}$ then $M$ accepts $w$. Observe that $M'$ accepts both $0w1$ (rule 1) and $1w^r0$ (rule 0), thus $\langle M', 0w1\rangle \in S_{TM}$.
On the other hand, if $\langle M,w\rangle \notin A_{TM}$, then also $M'$ doesn't accept $0w1$, and $\langle M', 0w1\rangle \notin S_{TM}$.

Observe that both $A_{TM}$ and $S_{TM}$ are $RE$ languages (which are not in $R$). You can also prove a reduction $S_{TM} \le A_{TM}$, by mapping $\langle M,w\rangle$ to $\langle M',w\rangle$, with $M'$ that runs $M$ on $w$ and then on $w'$. The proof is straightforward.

| cite | improve this answer | |

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.