Confusion in Reducibility

In Sipser's Theory of Computation book, it is stated while reducing ATM to REGULARTM

We let R be a TM that decides REGULARTM and construct TM S to decide ATM. Then S works in the following manner.

S = “On input , where M is a TM and w is a string:

1. Construct the following TM M2.

M2 = “On input x:

1. If x has the form 0n1n, 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 < M2>
3. If R accepts, accept ; if R rejects, reject .”`

My question is, shouldn't M2 reject x of the form 0n1n?

• No. Here's a hint. Try to work out the language of $M_2$ in terms of what $M$ does on $w$. (Also, it might help to think about what other languages could replace $0^n1^n$.) Commented May 23, 2014 at 15:33
• @Louis Umm okay, I understand that if M does not accept w, then check if x in M2 is of non-regular form, and then accept OR if M accepts w then simulate and return the result. What I don't understand is why do we have to return accept when x is of the form 0n1n? Commented May 23, 2014 at 15:59
• @AbdussamiTayyab: "then check if x in M2 is of non-regular form". No this isn't what happens. You need to think about the language of $M_2$, since $R$ decides something about the language of $M_2$, not what $M_2$ does on $x$. Commented May 23, 2014 at 17:31
• Oh! That's a pretty exact point! Thanks Louis! Commented May 23, 2014 at 18:34

Here, M2 hasn't been designed to accept Regular Languages. It has been designed to be used as argument of R. As per assumption that R can decide REGULARTM, R is free to reject M2 if the case arises. Remember, decidability includes both acceptance and rejection.

Update:
As per definition, R will accept only if argument TM accepts regular language. And, it will reject if argument TM accepts non-regular language. The setup of M2 harnesses this rejection property of R. If R hasn't rejected (as it can decide, it'll accept), it means point 2 of M2 was in action (which makes M accept w creating contradiction).

• But why do we return accept when x is of the form 0n1n? That is only the confusion? Commented May 23, 2014 at 16:03
• @Abdussami That just ensures that the Turning Machine is more general. Commented May 23, 2014 at 16:17
• Kindly elaborate 'general'. It must reject so the TM rejects. No? Commented May 23, 2014 at 16:21
• @AbdussamiTayyab The whole point is: If R really exists and it has accepted on M2 argument, it means point 2 of M2 specification is on action and M has accepted w. Point 1 is for otherwise thing. Commented May 23, 2014 at 16:24
• @AbdussamiTayyab R can only accept if it's argument TM accept regular language. If argument TM accepts non-regular language, R rejects as per definition. Commented May 23, 2014 at 16:33