I'm sure you all are familiar with Theorem 5.3 from Sipser's TOC book:


S = "On input (M,w) where M is a TM and w is a string:
1. Construct the code of TM M2 as follows:
M2 = "On input x:
(a) If x = 0n1n for some n ≥ 0, accept.
(b) If x = 0n1n, run M on w and if M accepts w, then accept."
2. Run R on (M2).
3. If R accepts, accept; if R rejects, reject."


I'm hoping to find an explanation as to how accepting (a) helps here. If x is of the form 0n1n then M2 accepts, R accepts, and S accepts. But we have accepted a nonregular language and M is not even considered. So R will accept this particular nonregular language (or)? epsilon star if M accepts w. Since R is obviously outside of M2 how does it know what caused M2 to accpet?


Does anyone have a different perspective on this? All of my searches seem to simply regurgitate Theorem 5.3 and don't offer much else.



REGULAR TM is undecidable
First of all, the undecidability of REGULAR\_TM follows immediately from Rice's theorem.


For a direct proof, Sipser gives a reduction from the language A\_TM. He constructs a decider R for A\_TM out of a decider for REGULAR\_TM, as follows.


R inputs the pair , where M is a TM and w is a string.
It constructs the TM M2, which accepts all strings of the form 0^n1^n and for all strings x not of this form, it runs M on w and accepts x if M accepted w.
[verify that all the constructions above are feasible in finite time]


What is the language accepted by M2? If M accepts w, M2 accepts every string (i.e., L(M2) is regular). If M does not accept w, M2 accepts only strings of the form 0^n1^n (i.e., L(M2) is not regular).


So a hypothetical decider for REGULAR-TM, when fed a description of M2, would as a by-product decide whether M accepts w.


