## REGULAR TM is undecidable

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.

-
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 2011 at 11:16
This is not really a research-level question. It would be more appropriate for math.stackexchange.com. – Qiaochu Yuan May 4 2011 at 11:28
Dear gjb, can I assume you are familiar with the closing lines of Tennyson's "Ulysses"? – Yemon Choi May 4 2011 at 12:00

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.

-
 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 2011 at 12:18 This is definitely not a research-level question, but I am glad my answer was helpful! – Aryeh Kontorovich May 4 2011 at 12:24

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.

-

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.

-

M2 accepts every string (i.e., L(M2) is regular), are you saying M2 is regular if it accept every string? why?

-