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.

  • 12
    $\begingroup$ 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... $\endgroup$ May 4 '11 at 11:16
  • $\begingroup$ This is not really a research-level question. It would be more appropriate for math.stackexchange.com. $\endgroup$ May 4 '11 at 11:28
  • 3
    $\begingroup$ Dear gjb, can I assume you are familiar with the closing lines of Tennyson's "Ulysses"? $\endgroup$
    – Yemon Choi
    May 4 '11 at 12:00
  • 1
    $\begingroup$ The item (b) in the question is incorrectly transcribed and should read instead: "If $x$ is not of the form $0^n 1^n$..." $\endgroup$ Sep 18 '13 at 12:46

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.

  • $\begingroup$ 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. $\endgroup$
    – methodmain
    May 4 '11 at 12:18
  • $\begingroup$ This is definitely not a research-level question, but I am glad my answer was helpful! $\endgroup$ May 4 '11 at 12:24
  • $\begingroup$ M2 accepts every string (i.e., L(M2) is regular), are you saying M2 is regular if it accept every string? why? $\endgroup$
    – user17561
    Sep 3 '11 at 0:43
  • $\begingroup$ If M2 accepts all strings, then R decides it is regular. $\endgroup$ Nov 12 '17 at 23:56

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.


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.

  • $\begingroup$ 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. $\endgroup$ 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.


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