# 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$.) – Louis May 23 '14 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? – Abdussami Tayyab May 23 '14 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$. – Louis May 23 '14 at 17:31
• Oh! That's a pretty exact point! Thanks Louis! – Abdussami Tayyab May 23 '14 at 18:34