# Problem with proving the undecidability of REGULAR$_{TM}$

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

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.

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

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 𝑀.

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