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, 2013 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, 2013 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, 2013 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, 2013 at 17:11
  • $\begingroup$ What is $A_{TM}$? Where did you get this from? $\endgroup$
    – Raphael
    Feb 11, 2013 at 17:35

3 Answers 3


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

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.

  • $\begingroup$ Clearly, $A_{TM}\neq S_{TM}$. I don't see how the first 3 lines of your answer make sense... $\endgroup$
    – nir shahar
    Jun 4, 2021 at 20:48
  • $\begingroup$ Very true, to be clear this is what the mapping function is supposed to do. They definitely are not equal $\endgroup$
    – IrateLion
    Jun 4, 2021 at 21:52
  • $\begingroup$ 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}$ $\endgroup$
    – nir shahar
    Jun 4, 2021 at 21:57
  • $\begingroup$ Edited it, thanks $\endgroup$
    – IrateLion
    Jun 4, 2021 at 22:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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