REGULAR TM is undecidable [closed]

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

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.

Answer 3

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 4

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.