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

1. REG is recursively enumerable but Co-REG is not
2. REG is not recursively enumerable but Co-REG is
3. 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 ?

Answer 1

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$