Reduce ATM to the language of TM encodings where if the TM accepts w then the TM accepts ww

Question

Today I did a test in my class, the trace was:

Prove that the language $L =\{\langle M\rangle\mid \forall w \in \{0,1\}^\ast: M \text{ accepts }w\implies M \text { accepts }ww \}$, is undecidable with a reduction from $A_{\mathrm{TM}}$.
Hint: You can suppose that $w\in \{0,1\}^*$

I answered:

Suppose that $L$ is decidable. Therefore, there is a TM $R$ such that $L(R)= L$, so we can construct a new TM $S$ that decides $A_{\mathrm{TM}}$.

First, construct $N$ as follows:
$\\$
"On input $x$:

• if $x$ is of the form $ww$, accept
  
• otherwise, run $M$ on $w$ and do what $M$ does.
  

Now we can construct $S$ as follows:

• Construct $N$ as above.
• Run $R$ on $N$; if $R$ accepts, accept; otherwise, reject.

Now I know this isn't correct, but I don't why. More generally, how to recognize a language of a reduction? For example, in my reduction, $S\text{ accepts } w \iff \text{the language of } N\text{ is ?} \iff \langle M,w\rangle \in A_{\mathrm{TM}} $
I think I'm missing something about reductions but I don't know what.

Answer 1

First of all, assume the TM $S$ receives a (correctly encoded) instance $\langle M, w \rangle$ of $A_{\text{TM}}$. $N = N_{M,w}$ must be constructed in terms of $M$ and $w$, that is, its description depends on the problem instance $\langle M, w \rangle$. (It is sloppy to just describe $N$ without having fixed this instance first.)

Your overall proof structure is correct, only you made a couple of mistakes in the constructions of $N = N_{M,w}$ and $S$. Instead you should have for $N$:

On input $x$:

• If $x$ is of the form $w'w'$ for some $w' \in \{0,1\}^\ast$, reject;
• Otherwise, simulate $M$ on input $w$ and do what $M$ does.

Why this? Consider the following: $$\begin{align*} \langle N \rangle \in L &\iff \forall w' \in \{0,1\}^\ast: (w' \in L(N) \implies w'w' \in L(N)) \\ &\iff \forall w' \in \{0,1\}^\ast: w' \not\in L(N) \lor w'w' \in L(N) \\ &\iff \forall w' \in \{0,1\}^\ast: w' \not\in L(N) \\ &\iff \not \exists w' \in \{0,1\}^\ast: w' \in L(N) \\ &\iff \lnot (\text{$M$ accepts input $w$}) \end{align*}$$

The third equivalence is the reason behind constructing $N$ so as to reject inputs of the form $w'w'$. The last equivalence holds because not all strings are of the form $w'w'$ for some $w' \in \{0,1\}^\ast$.

To complete the construction of $S$, have it feed $\langle N \rangle$ to $R$ and accept if $R$ rejects and reject otherwise (i.e., $S$ returns the opposite of what $R$ returns). By the equivalences above, $S$ reduces $A_{\text{TM}}$ to $L$, so $L$ must be undecidable.

---

As to your more general question regarding reductions: Unfortunately, I am afraid these kind of problems are rather tricky in of themselves. (I suppose that, at the core of it, the problem is that we are dealing with paradoxes, which are, of course, very nasty little things.) Nevertheless, Rice's theorem generalizes a great deal of these questions and makes it much simpler to prove something reduces to $A_{\text{TM}}$ or the halting problem.