# Mapping reductions for dummies

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?

• Observe that $S_{TM}$ accepts $w$ if and only if it accepts $w^R$. Feb 11, 2013 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. Feb 11, 2013 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, 2013 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$. Feb 11, 2013 at 17:11
• What is $A_{TM}$? Where did you get this from?
– Raphael
Feb 11, 2013 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.

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.

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.

• Clearly, $A_{TM}\neq S_{TM}$. I don't see how the first 3 lines of your answer make sense... Jun 4, 2021 at 20:48
• Very true, to be clear this is what the mapping function is supposed to do. They definitely are not equal Jun 4, 2021 at 21:52
• Then you probably forgot $f(x)$ in the first equation, since it is logically equivalent to $A_{TM}=S_{TM}$. You might have meant: $\forall x\in\Sigma^*: x\in A_{TM}\iff f(x)\in S_{TM}$ Jun 4, 2021 at 21:57
• Edited it, thanks Jun 4, 2021 at 22:11