Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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