Let M range over turing machine descriptions .Consider the set REG={M|L(M) is a regular set} which of the statements are true?

Question

The complement of REG is Co-REG

REG is recursively enumerable but Co-REG is not
REG is not recursively enumerable but Co-REG is
Both are recursively enumerable 4.None of them are recursively enumerable

According to me if the language accepted by turing machine is a regular set then clearly the complement of regular set should be a regular set as well so then why are we using the terminology of recursively enumerable sets here ?

Be carefull here, since we are not manipulating regular sets, but the set REG of TM that recognize regular sets (that is itself a language). — sapristi, Nov 29 '15 at 15:44
So then complement will consist of all the turing machines which do not accept regular set and since all the turing machines accept it so such turing machine won't exist ,so then what can I conclude from this now — Radha Gogia, Nov 29 '15 at 16:05
Oh no you can't ! You should revise your course about TM, and languages.
Anyway, this question is quite difficult. The 3. is easy to disprove using Rice's theorem, you could try writing why it is so. I will give the full answer with proof when I can.

To give a hint : for REG to be in RE, there would have to be an algorithm with input a turing machine M, and output yes if L(M) is regular (if not, the algorithm might not terminate). How would you do that ? — sapristi, Nov 29 '15 at 16:12
I guess first problem REG will be undecidable since it reduces to a problem of finding whether language accepted by turing machine is regular or not and so it is recursively enumerable and complement of recursively enumerable which is Co-REG will not be recursively enumerable .Am I correct ? — Radha Gogia, Nov 29 '15 at 16:17
Some of the reasoning is correct, but why are you saying REG is in RE ? — sapristi, Nov 29 '15 at 16:22
Since the turing machine may hault saying yes and may go into infinite loop — Radha Gogia, Nov 29 '15 at 16:25
Now I am getting confused ,please clarify this ,I am stucked badly — Radha Gogia, Nov 29 '15 at 16:36
Let us state what we know :

According to Rice's theorem, neither REG nor Co-Reg are decidable (= recursive).

If both REG and Co-Reg were RE, then they would be recursive.

We conclude we can't have both in RE. — sapristi, Nov 29 '15 at 16:40

score 2 · Accepted Answer · answered Nov 29 '15 at 17:55

Let us first prove that REG is not RE. I will use the book Introduction to Automata Theory, Languages and Computation by Hopcroft and Ullman.

$\newcommand{\S}{\mathcal S}$ Let $\S \subset RE$ a set of recursive languages, and $L_{\S} = \{ <M>, L(M) \in \S \}$ ($<M>$ denotes here the an encoding of the TM M, so that we clearly define $L_{\S}$ as a language.

We are interested to know whether $L_{REG} \in RE$.

Theorem 1

If $L_{\S} \in RE$, then $(\forall L \in L_{\S}), (\forall L' \in RE$ such that $L \subset L')$, we have $L' \in \S$.

Proof that $L_{REG} \not \in RE$ using theorem 1

Be $l_1 \in REG$, there are clearly languages containing $l_1$ that are not regular, and as such $L_{REG} \not \in RE$.

Proof of the theorem 1

Be $L_1 \in \S, L_2 \in RE$ such that $L_1 \subset L_2$ and $L2 \not \in \S$. Be $M_1, M_2$ turing machines recognising $L_1$ and $L_2$ respectively.

Let us suppose $L_{\S} \in RE$, and be $M_{\S}$ a TM that accepts $L_{\S}$

Reminder: Be $L_u = \{ <M,w>, \text{ M accepts w } \}$ the universal language. Neither $L_u$ nor $\bar{L_u} = \{ <M,w>, \text{ M does not accept w } \}$ are decidable.

To get a contradiction in our hypothesis, we will show $\bar{L_u}$ is decidable.

Be $A$ be the TM that takes $<M,w>$ as input, and the following machine $M'$ as an output :

We have the following :

If $w \in L(M)$, then $L(M') = L_2 \not \in L_{\S}$
If $w \not \in L(M)$, then $L(M') = L_1 \in L_{\S}$

So that $L(M') \in L_{\S}$ iff $w \not \in L(M)$.

We know build a second TM :

Putting everything together, we get that this TM accepts $<M,w>$ iff $L(M') \in \S$ iff $M$ does not accept $w$. This TM decides $\bar{L_u}$, which is impossible.

We also have $L_{Co-REG} \not \in RE$ from another theorem which I will not prove here (it is in the same book):

Theorem 2

If $\S$ contains an infinite language $L$ such that there is no finite subset of $L$ in $\S$, then $L_{\S} \not \in RE$.

Proof that $L_{Co-REG} \not \in RE$

There clearly are infinite languages in Co-REG. Let us pick one : $L$. Since any finite language is in REG, there is no finite subset of $L$ in Co-REG, and thus Co-REG $\not \in RE$