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

| cite | improve this question | | | | |
$\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.

| cite | improve this answer | | | | |
$\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 𝑀.

| cite | improve this answer | | | | |
$\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 '19 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 '19 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.