Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question
    
Observe that $S_{TM}$ accepts $w$ if and only if it accepts $w^R$. –  Pål GD Feb 11 '13 at 16:25
    
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. –  user6821 Feb 11 '13 at 16:45
    
Just a typo: if the reduction is from $A_{TM}$ to $S_{TM}$ then it "is supposed to solve $A_{TM}$ using $S_{TM}$". –  Vor Feb 11 '13 at 16:58
    
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$. –  Pål GD Feb 11 '13 at 17:11
    
What is $A_{TM}$? Where did you get this from? –  Raphael Feb 11 '13 at 17:35

2 Answers 2

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.

share|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).

proof.
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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.