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

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$ – Abdussami Tayyab May 23 '14 at 16:03
  • $\begingroup$ @Abdussami That just ensures that the Turning Machine is more general. $\endgroup$ – Babbage's Difference Engine May 23 '14 at 16:17
  • $\begingroup$ Kindly elaborate 'general'. It must reject so the TM rejects. No? $\endgroup$ – Abdussami Tayyab May 23 '14 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$ – Babbage's Difference Engine May 23 '14 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$ – Babbage's Difference Engine May 23 '14 at 16:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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