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?

  • 1
    $\begingroup$ 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$.) $\endgroup$
    – Louis
    May 23, 2014 at 15:33
  • $\begingroup$ @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? $\endgroup$ May 23, 2014 at 15:59
  • 1
    $\begingroup$ @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$. $\endgroup$
    – Louis
    May 23, 2014 at 17:31
  • $\begingroup$ Oh! That's a pretty exact point! Thanks Louis! $\endgroup$ May 23, 2014 at 18:34

1 Answer 1


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.

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).

  • $\begingroup$ But why do we return accept when x is of the form 0n1n? That is only the confusion? $\endgroup$ May 23, 2014 at 16:03
  • $\begingroup$ @Abdussami That just ensures that the Turning Machine is more general. $\endgroup$ May 23, 2014 at 16:17
  • $\begingroup$ Kindly elaborate 'general'. It must reject so the TM rejects. No? $\endgroup$ May 23, 2014 at 16:21
  • $\begingroup$ @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. $\endgroup$ May 23, 2014 at 16:24
  • 1
    $\begingroup$ @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. $\endgroup$ May 23, 2014 at 16:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.