Undecidability of REGULAR_TM

Question

In case you have Sipser's Introduction to the Theory of Computation 3rd edition, I am asking specifically about the proof of theorem 5.3, how the language REGULAR_TM is undecidable. \begin{equation} REGULAR_{TM} = \{\langle M\rangle | M \text{ is a } TM \text{ and } L(M) \text{ is a regular language}\} \end{equation} Here is the proof from Sipser:

We let $R$ be a $TM$ that decides $REGULAR_{TM}$ and construct $TM$ $S$ to decide $A_{TM}$ (the acceptance problem for Turing Machines). Then $S$ works in the following manner:

$S = $ "On input $\langle M, w\rangle$, 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 $\langle M_2\rangle$

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

I get that the idea is to show that if we can decide $REGULAR_{TM}$ then we can decide $A_{TM}$, which is a contradiction and hence $REGULAR_{TM}$ is undecidable. I see the big picture idea with $M_2$: in step 1, $M_2$s construction gives a nonregular language and step 2 in $M_2$s construction gives a regular language if $M$ accepts $w$. This looks to me as if we have two disjoint cases in which $L(M_2)$ can be regular or nonregular, and then when $R$ is given the encoding of $M_2$ it can decide whether $M_2$'s language is nonregular or regular and specifically regular iff $M$ accepts $w$, hence deciding $A_{TM}$.

1. What I do not understand is how step 2 in $M_2$'s construction gives a regular language if $M$ accepts $w$.
2. Sipser says that if $M$ accepts $w$ then $M_2$ will accept $\sum^*$ (which is short for $(0 \cup 1)^*)$ which is a regular expression and hence a regular language. I do not see how this works either...

Thanks for all the help and let me know if you need any clarifications.

Answer 1

Remember that when you construct $M_2$, you're embedding a constant TM $M$ to be run on a constant string $w$. $M_2$ is then accepting any string $x$ iff $M$ accepted $w$, which makes $L(M_2) = \Sigma^*$, a regular language. Note that all strings of the form $0^n1^n$ are obviously within $\Sigma^*$.

Now, suppose $M$ did not accept $w$, then case 2 of $M_2$ would simply be to "reject otherwise". Thus $L(M_2)$ is now only strings of the form $0^n1^n$, which is not regular.

Thus, if $R$ can decide whether $M_2$ is regular, it also could indirectly decide whether some TM $M$ accepts a string $w$.