Mapping reductions for dummies

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

Ran has a good short answer, so I'll do a semi-formal proof for this based on the provided $M'$:
The goal of a mapping reduction is to show that for some function F \begin{equation} \forall x \in \Sigma^*, x \in A_{TM} \Longleftrightarrow F(x) \in S_{TM} \end{equation} In other words, every x (encodings of M with a string w) in $A_{TM}$ has to be in $S_{TM}$ and every x that is not in $A_{TM}$ must not be in $S_{TM}$
Case 1: $ \langle M,w\rangle \in A_{TM} \implies \langle M'\rangle \in S_{TM} $
$\quad$ $M'$ will accept x if it is 01 of course. For anything that is not 01, it will
$\quad$ proceed to run $M$ on it, and since we're assuming that $\langle M,w\rangle \in A_{TM}$,
$\quad$ every other x will also be accepted by $M'$. Therefore, $L(M') = \Sigma^*$
$\quad$ which implies that every word $w$ has a $w^R$ in it, meaning that $ \langle M'\rangle \in S_{TM}$.

Case 2: $\langle M,w\rangle \notin A_{TM} \implies \langle M'\rangle \notin S_{TM}$
$\quad$ Case 2.1: $\langle M,w\rangle$ fails the input typecheck (assuming we have one) so we output a $const_{out}$ which is
$\quad \quad$ guaranteed to not be in $S_{TM}$.
​ $ \quad$ Case 2.2: $M$ halts and rejects on $w$
$\quad \quad$ We always accept 01 since that is given. But now when we run $M$ on any input x that is not 01, we will
$\quad \quad$ reject that x since $w$ is not in $M$. Therefore, $L(M') = \{01\}$
$\quad \quad$ which is not in $S_{TM}$ since the reverse word, 10, is not present in $L(M')$.
$\quad$ Case 2.3: $M$ loops on $w$
$\quad \quad$ Same idea as when it halts and rejects, since $w \notin M$ we only have the word 01 ever begin accepted
$\quad \quad$ and so $\langle M'\rangle$ will not be in $S_{TM}$
(We can also conclude this now!). Since we've shown that we can decide $S_{TM}$, we can also decide $A_{TM}$ since we can map any input of $A_{TM}$ to $S_{TM}$. But this is a contradiction since $A_{TM}$ is undecidable. Therefore, $S_{TM}$ is undecidable as well.