Hello the proof of the Spiser's book (introduction to theory of computation): PROOF 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 (M, w), 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 o^i 1^i , accept. 2. If x does not have this form, run M on input w and accept if M accepts w." 2. R on input (M2 ). 3. Run R if accepts, accept; if R rejects, reject." I don't understand how it works. If x has that form accept and R will reject because 0^i1^i is not regular. What happens when M rejects?