MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm sure you all are familiar with Theorem 5.3 from Sipser's TOC book:

S = "On input (M,w) where M is a TM and w is a string: 1. Construct the code of TM M2 as follows: M2 = "On input x: (a) If x = 0n1n for some n ≥ 0, accept. (b) If x = 0n1n, run M on w and if M accepts w, then accept." 2. Run R on (M2). 3. If R accepts, accept; if R rejects, reject."

I'm hoping to find an explanation as to how accepting (a) helps here. If x is of the form 0n1n then M2 accepts, R accepts, and S accepts. But we have accepted a nonregular language and M is not even considered. So R will accept this particular nonregular language (or)? epsilon star if M accepts w. Since R is obviously outside of M2 how does it know what caused M2 to accpet?

Does anyone have a different perspective on this? All of my searches seem to simply regurgitate Theorem 5.3 and don't offer much else.

share|cite|improve this question

closed as off-topic by Ricardo Andrade, Andrey Rekalo, Benjamin Steinberg, Chris Godsil, Ryan Budney Sep 20 '13 at 4:25

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question does not appear to be about research level mathematics within the scope defined in the help center." – Ricardo Andrade, Andrey Rekalo, Benjamin Steinberg, Chris Godsil, Ryan Budney
If this question can be reworded to fit the rules in the help center, please edit the question.

Dear gjb, I'm incredibly flattered by your assumption that I am "familiar with Theorem 5.3 from Sipser's TOC book". I daren't confess to you the sad truth... – Georges Elencwajg May 4 '11 at 11:16
This is not really a research-level question. It would be more appropriate for – Qiaochu Yuan May 4 '11 at 11:28
Dear gjb, can I assume you are familiar with the closing lines of Tennyson's "Ulysses"? – Yemon Choi May 4 '11 at 12:00
The item (b) in the question is incorrectly transcribed and should read instead: "If $x$ is not of the form $0^n 1^n$..." – Ricardo Andrade Sep 18 '13 at 12:46
up vote 5 down vote accepted

First of all, the undecidability of REGULAR_TM follows immediately from Rice's theorem.

For a direct proof, Sipser gives a reduction from the language A_TM. He constructs a decider R for A_TM out of a decider for REGULAR_TM, as follows.

R inputs the pair , where M is a TM and w is a string. It constructs the TM M2, which accepts all strings of the form 0^n1^n and for all strings x not of this form, it runs M on w and accepts x if M accepted w. [verify that all the constructions above are feasible in finite time]

What is the language accepted by M2? If M accepts w, M2 accepts every string (i.e., L(M2) is regular). If M does not accept w, M2 accepts only strings of the form 0^n1^n (i.e., L(M2) is not regular).

So a hypothetical decider for REGULAR-TM, when fed a description of M2, would as a by-product decide whether M accepts w.

share|cite|improve this answer
I strove for a week or so to seek an understanding of this theorem and yet did not yield an understanding of this theorem. Thank you for your explanation Mr. Kontorovich. R accepts or rejects based on the language of M2. – gjb May 4 '11 at 12:18
This is definitely not a research-level question, but I am glad my answer was helpful! – Aryeh Kontorovich May 4 '11 at 12:24
M2 accepts every string (i.e., L(M2) is regular), are you saying M2 is regular if it accept every string? why? – user17561 Sep 3 '11 at 0:43

We know that the language A_TM is undecidable. Let us just suppose that REGULAR_TM is decidable. If I can build a decider for A_TM, using a decider for REGULAR_TM, it is clear that REGULAR_TM is not decidable. This is how to build a decider for A_TM, M_A using a decider for REGULAR_TM, M_R:

M_A = On input , run M_R on input .

M' is a TM that is build using the input given to M_A as follows: 1. If w is on the form 0^n1^n, accept 2. Simulate that M runs w. If M accepts, accept. 3. Reject

So what happens here? The TM M' is a machine that will never execute, we only need it because M_R can predict whether L(M') is a regular language. So when will L(M') be regular? Notice that if M accepts w, L(M') contains every string since it will accept when reaching 2. There is indeed the possibility that M' will never halt. In that case, only accept strings on the form 0^1n^1, which means that L(M') will not be regular.

So if M accepts w, L(M') contains all strings. The language of all strings is a regular language. In any other case, L(M') will not be a regular language. We can also say that L(M') is regular, if and only if M accepts w. Since M_R can tell us if L(M') is regular, we just run M_R on input . If it tells us that L(M') is regular, we know that M_A accepts w. If not, M_A rejects w. That is in fact a decider for A_TM.

share|cite|improve this answer

Since Sigma* (Sigma = alphabet set) is a regular language, for R to decide whether M2 accepts a regular language it must consider all possible inputs (Sigma ), including 0^n1^n and other nonregular languages. So if M accepts w, M2 accepts not only 0^n1^n kind of inputs but Sigma. But if M does not accept w, M2 will accept just 0^n1^n strings. Hope it helps.

share|cite|improve this answer
The asterisks in Sigma* in this answer were interpreted as markdown. Consequently, the asterisks do not show up, and instead the text appears in italic. – Ricardo Andrade Sep 18 '13 at 13:12

I think we should think this way. If M2 is a machine that accepts regular languages, it must accept some string other than 0n1n, which means M must accpet w.

If M does not accept w, M2 will not accept any regular string, thus L(M2) is irregular.

share|cite|improve this answer

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