0
$\begingroup$

Sipser in his book provided the following proof for undecidability of REGULAR$_{TM}$:

S = “On input $<M,w>$, where $M$ is a TM and w is a string:

  1. Construct the following TM $M_2$.

    $M_2$= “On input $x$:

    1. If $x$ has the form $0^n1^n$, accept .

    2. If $x $ does not have this form, run $M$ on input $w$ and accept if $M$ accepts $w$.”

  2. Run $R$ on input $<M_2>$.

  3. If $R$ accepts, accept; if $R$ rejects, reject .”

and it also states:

Note that the TM $M_2$ is not constructed for the purposes of actually running it on some input. We construct $M_2$ only for the purpose of feeding its description into the decider for REGULAR$_{TM}$ that we have assumed to exist.

So it means we don't run the $M$ on $w$ at all. I would like to know why when the $M_2$ accepts regular languages we conclude that the $M$ accepts $w$ while we never run $M$ on $w$? The reduction must have a meaningful relationship between the problems. I can't understand this relation in this problem.

thanks

$\endgroup$
3
$\begingroup$

Note $M_2$ is constructed based on $\langle M,w\rangle$. That is to say, different $\langle M,w\rangle$ may result in different $M_2$.

If $M$ accepts $w$, then $M_2$ will accept any string (if the input has the form $0^n1^n$, $M_2$ accepts it at the first step, otherwise $M_2$ accepts it at the second step), thus $M_2$ accepts a regular language.

If $M$ does not accept $w$, then $M_2$ will only accept string of the form $0^n1^n$ (if the input has the form $0^n1^n$, $M_2$ accepts it at the first step, otherwise $M_2$ skips the first step, and will not accept it at the second step), thus $M_2$ accepts a non-regular language.

So we can conclude $M$ accepts $w$ iff $M_2$ accepts a regular language.

$\endgroup$
  • $\begingroup$ When we don't run $M_2$ we don't run $M$ on $w$. so it doesn't matter what $M$ outputs on $w$ $\endgroup$ – M a m a D Apr 23 '18 at 9:22
  • $\begingroup$ What $M$ outputs on $w$ is a property of $\langle M,w\rangle$. It doesn't matter whether you run it or not. $\endgroup$ – xskxzr Apr 23 '18 at 9:25
0
$\begingroup$

Note that the TM 𝑀2 is not constructed for the purposes of actually running it on some input.

I think the statement above is wrong, because:

On input <𝑀,𝑤>, the input 𝑥 which is feed to 𝑀2 could be always a string without the form 0𝑛1𝑛, for example, 𝑥 always be 1, then S still can decide 𝑤 on 𝑀.

$\endgroup$
  • $\begingroup$ What do you mean by "S still can decide w on M"? In addition, I think this is more a comment than an answer. $\endgroup$ – xskxzr Aug 7 at 9:09
  • $\begingroup$ On every 𝑤 on 𝑀, we construct a M2 whose input is always 1, then if R decide M2, S decide 𝑀 on 𝑤. $\endgroup$ – Anonemous Aug 7 at 9:19

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.