2
$\begingroup$

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$?

$\endgroup$
  • $\begingroup$ What is $A_{TM}$ ? Can you try to improve the readability? What are you trying to prove? What is the purpose of your construction? $\endgroup$ – babou May 30 '15 at 11:55
  • $\begingroup$ Of course. $A_{TM}$ is a common notation for the (undecidable) language $$\{ \langle M,w \rangle \ | \ \text { TM M accepts w } \}$$ $\endgroup$ – Elimination May 30 '15 at 13:22
  • $\begingroup$ I am trying to prove by contradiction (using reduction to $A_{TM}$) that $L$ is undecidable language. $\endgroup$ – Elimination May 30 '15 at 13:38
  • 2
    $\begingroup$ Thanks. That is what is needed so that people understand what you are at.`It should be in the text of your question, explaining why you are doing all that. Also, do not assume too much in notations when talking to the planet, it is sometimes noted $ATM$, but ATM can also mean Alternating Turing Machine (whatever that is). I personally did not know this notation as standard, and I noticed on the web that many people still give the definition. $\endgroup$ – babou May 30 '15 at 13:56
  • 1
    $\begingroup$ "In computability theory, a Turing reduction from a problem A to a problem B, is a reduction which solves A, assuming the solution to B is already known". You assume decidability of $L$ is known. The fact that $M$ does not halt, or rejects is immaterial. What you want is that the language accepted by $M_1$ is $\{01\}$ iff $M$ accepts $w$ (and is $\emptyset$ otherwise. If $M$ loops, thus not acceptin $w$, then $M_1$ loops on any input, recognizing $\emptyset$. Hence $M_L$ will accept $\langle M_1 \rangle$, so that $M_{ATM}$ will reject. $\endgroup$ – babou May 30 '15 at 15:03
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Now, I am curious to see what happens. $\endgroup$ – babou May 30 '15 at 15:20
  • 1
    $\begingroup$ I spent considerable time trying to explain to the OP how to make a question clearer. But I am afraid it was wasted. The problem is that we can work out what he intends, but the work is useless for further users as understanding what is the issue is to hard. Hence they will not bother reading at all. The question should not have to be explained in answers ,,, Working on question quality is the proper way to say "please" and "thank you" cc @Elimination $\endgroup$ – babou May 31 '15 at 14:13
  • $\begingroup$ I appreciate your criticism, @babou $\endgroup$ – Elimination May 31 '15 at 14:40
  • 1
    $\begingroup$ Thanks. I edited your question to make it easier for future users. You can thus see what I meant. Good luck. $\endgroup$ – babou May 31 '15 at 14:46
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This solution doesn't work: R will always accept on $M_w$, since either $L(M) = \emptyset$ or $L(M) = \{ 010 \}$, and in both cases $L(M)$ is closed under string reversal. $\endgroup$ – Yuval Filmus Aug 11 '17 at 20:25
  • $\begingroup$ Can you please clarify - $L(M) $ is closed under string reversal ? (Sipser): A collection of objects is closed under some operation if applying that operation to members of the collection returns an object still in the collection. Now empty set contains no elements. $\endgroup$ – acagu Aug 11 '17 at 20:40
  • $\begingroup$ The empty set is closed under reversal vacuously. You can prove this using the definition – if you apply reversal to a member of the collection, you get another member of the collection. You can easily check that this holds for the empty set. $\endgroup$ – Yuval Filmus Aug 11 '17 at 20:44

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.