0
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • 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
    Commented 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$
    – Abdussami Tayyab
    Commented 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
    Commented May 23, 2014 at 17:31
  • $\begingroup$ Oh! That's a pretty exact point! Thanks Louis! $\endgroup$
    – Abdussami Tayyab
    Commented May 23, 2014 at 18:34

1 Answer 1

Reset to default
1
$\begingroup$

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

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

Your Answer

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

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