1
$\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$

2 Answers 2

4
$\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$
6
  • $\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, 2018 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, 2018 at 9:25
  • $\begingroup$ So, what is the language of M2? $\endgroup$
    – There
    Apr 15 at 14:29
  • $\begingroup$ I think it'd be helpful to see a list of example inputs accepted and rejected by M, and how M2 reacts. $\endgroup$
    – There
    Apr 15 at 14:42
  • $\begingroup$ "M accepts w iff M2 accepts a regular language." Doesn't this mean that for certain values of w, M rejects w by the above algorithm, when in fact M would typically accept w? $\endgroup$
    – There
    Apr 15 at 14:46
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$
2
  • $\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, 2019 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, 2019 at 9:19

Your Answer

By clicking β€œPost Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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