Reduction and decidability

Question

Consider the following language: $$ L = \{ \langle M \rangle \ |\ M \text { accepts } w \text { whenever it accepts } w^R \}$$

I am trying to understand the following proof that this language $L$ is undecidable.

The proof proceeds by contradiction, by reducing to $L$ the language $A_{TM}=\{\langle M,w \rangle\mid M\text{ accepts }w\}$ known to be undecidable. It goes as follows:

Suppose that $L$ is decidable, then there's a TM $M_L$, that decides $L$

Thus we can build $M_{ATM}$ to decide $A_{TM}$ as follows:

1. Let $\langle M, w \rangle$ be an input for $M_{ATM}$.
2. Construct a machine, $M_1$ which on input $x$: Simulate $M$ on $w$; if $M$ rejects $w$, $reject$. If $M$ accepts $w$, $accept$ if $x=01$, $reject$ otherwise.
3. Simulate $M_L$ on input $\langle M_1 \rangle$.
4. $accept$ if $M_L$ rejects. $reject$ otherwise.

Since $A_{TM}$ is not decidable, we have a contradiction, which implies that $L$ cannot be decidable.

However there is a point of the proof I do not understand.

My question is: What happens if $M$ gets into a loop on some $w$?

Answer 1

In many problems like this, it's often a bad idea to base your construction on both acceptance and rejection. Try rewriting your $M_1$ in this form

M1(x) =
   simulate M on w
   if M accepts w
      if x = 01
         accept

Now the important thing is that

1. If $M$ accepts $w$ (i.e., if $\langle M, w\rangle\in A_{TM}$) then $L(M_1)=\{01\}$.
2. If $M$ fails to accept $w$, either by rejecting or by running forever, then $M_1$ will accept nothing, so $L(M_1)=\varnothing$

Now if $L$ were decidable with decider $M_L$, then you can use the decider and $M_1$ to build a decider, $M_A$, for $A_{TM}$ as you suggested:

MA(<M>, w) = 
   Construct M1 as above
   if ML accepts <M1>
      reject
   else if ML rejects <M1>
      accept

Now we have

1. If $M$ accepts $w$, then $L(M_1)=\{01\}$ so $M_L$ will reject $M_1$ and hence $M_A$ will accept $\langle M, w\rangle$.
2. If $M$ doesn't accept $w$, then $L(M_1)=\varnothing$ so $M_L$ will accept $M_1$ and hence $M_A$ will reject $\langle M, w\rangle$.

In short, $M_A$ is indeed a decider for $A_{TM}$, an undecidable language, meaning that $L$ must not be decidable.

Answer 2

In this reduction of $A_{TM}=\{\langle M,w \rangle\mid M\text{ accepts }w\}$ to $L$, what matters in the construction of the Turing machine $M_1$ is that the language accepted by $M_1$ is $\{01\}$ iff $M$ accepts $w$, and is $\emptyset$ otherwise.

Whether $M$ does not halt on input $w$, or halts rejecting it, does not make any difference. In both cases, the language accepted by $M_1$ is $\emptyset$, thus satisfyiing the definition for $L$. Hence $M_L$ will accept $\langle M_1 \rangle$, so that $M_{ATM}$ will reject.

Answer 3

You are trying to prove that $L$ is undecidable by showing $A_{tm}\le L$.

For this reduction to be valid, you need to convert each input $(\langle M \rangle, w)$ of $A_{tm}$ into an input $\langle M_1 \rangle$ (using your notations) for $L$ so that $$ (\langle M \rangle, w) \in A_{tm} \quad\text{ iff }\quad \langle M_1 \rangle \in L$$

Equivalently, such a reduction shows that if you can decide $L$ you will be able to decide $A_{tm}$: simply you convert the input of $A_{tm}$ to an equivalent input of $L$ and run $M_L$ on it.

So the question that hides in your post, is how to convert the inputs. Let's see what happens in each case:

1. case I: $(\langle M \rangle, w) \in A_{tm}$.
   In this case $M_1$ will just run $M$ on $w$ (which ends in an accepting state, and specifically, always halts), and then only accepts $x=01$. Therefore $M_1$ is not in $L$.

2. case II: $(\langle M \rangle, w) \notin A_{tm}$.
   As you mention, there are 2 cases here: wither $M$ rejects $w$ or it never halts. In both cases, $M_1$ never accept a single word: either it rejects everything, or it never halts (and then also no input is ever accepted). Therefore $M_1$ is in $L$ (vacuously satisfying the requirement).

So this goes the opposite way from the "iff" statement I wrote above, but that's fine because the final decision of your $M_{ATM}$ is the opposite of the decision of $M_L$ on $M_1$, which fixes this negaiton. So everything works fine, and the proof is valid. Makes sense?

Answer 4

Wrong solution ( based on the comment below )

L={⟨M⟩ | M accepts w whenever it accepts $w^R$}. Proof by contradiction. Assume that L is decidable and let $R$ be a decider for it. We will construct decider $S$ for $A_{tm}$, using $R$ as a subrouting. Note that $A_{tm}$ = {<M,w> | M is a TM and M accepts w}.

S = on input <M,w>
constructs M_w = on input x
if x!=010 reject
else run M on w
 if M accepts w => accept
 else reject
Run R on M_w
if R accepts => accept
if R rejects => reject

Note: if $M$ accepts $w$ then $L(M_w)$ = {010} , $R$ ran on $M_w$ will accept, therefore $S$ will accept. if $M$ rejects or loops on $w$ then $L(M_w)$ = empty set , $R$ ran on $M_w$ will reject, therefore $S$ will reject. We have built a decider for $A_{tm}$, since we know that $A_{tm} $ is undecidable our assumption was wrong => L is undecidable.

Edited Solution>>>

L={⟨M⟩ | M accepts w whenever it accepts $w^R$}. Proof by contradiction. Assume that L is decidable and let $R$ be a decider for it. We will construct decider $S$ for $A_{tm}$, using $R$ as a subrouting. Note that $A_{tm}$ = {<M,w> | M is a TM and M accepts w`}.

S = on input <M,w>
constructs M_w = on input x
run M on w
 if M accepts w => reject
 else  => accept
Run R on M_w
if R accepts => accept
if R rejects => reject

Note: if $M$ accepts $w$ then $M_w$ will reject on all input $L(M_w)$ = empty set, $R$ ran on $M_w$ will accept, therefore $S$ will accept. if $M$ rejects or loops on $w$ then $L(M_w)$ = {$\Sigma^*$} , $R$ ran on $M_w$ will reject , therefore $S$ will reject. We have built a decider for $A_{tm}$, since we know that $A_{tm} $ is undecidable our assumption was wrong => L is undecidable.