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.

  • $\begingroup$ Is $L$ supposed to be defined in terms of a fixed $w$? Or is $w$ quantified as in "$\forall w \in \{ 0, 1 \}^\ast : M \text{ accepts } w \implies M \text{ accepts } ww$"? $\endgroup$
    – dkaeae
    Nov 29 '18 at 15:27
  • $\begingroup$ It's ∀w∈{0,1}^∗ $\endgroup$
    – Emanuele
    Nov 29 '18 at 15:31

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.

  • $\begingroup$ Thank you so much! I know about Rice's theorem but the teacher doesn't want us to use it. $\endgroup$
    – Emanuele
    Nov 29 '18 at 16:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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