Are $CF_{TM}$, $\space $ $\overline{CF_{TM}}$ Turing-recognizable?

Question

I have searched the site well through, and also using Google and notes and couldn't find an answer to a question I am wondering about.

Given:

$$CF_{TM} =\{ \langle M \rangle \mid \text{$M$ is a TM description and $L(M)$ is a context-free language} \}$$

Are $CF_{TM}$,$\space $ $\overline{CF_{TM}}$ Turing-recognizable?

In order for a machine to be turing recognizable, there should exist a Turing machine that will halt and accept only string on that language, and for strings no in that language, it should reject or not halt at all.

So i am truly wondering about the relationship between context free languages and being Turing-recognizable, are $CF_{TM}$, $\space $ $\overline{CF_{TM}}$ Turing-recognizable?

Answer 1

This question describes a nice situation to introduce a partial version of the generalized Rice's theorem.

A partial version of the generalized Rice's Theorem

For $S$ be a subset of Turing-recognizable languages, let $L_S$ be the set of TMs that recognize a language in $S$, that is, $$L_S = \{ \langle M \rangle \mid L(M) \in S \}.$$ Suppose $L_1 \in S$, $L_1 \subset L_2$ and $L_2 \not\in S$. Then $L_S$ is not Turing-recognizable.

$CF_{\text{TM}}$ is not Turing-recognizable.

$CF_{\text{TM}}=L_{\text{CFL}}$, where $\text{CFL}$ is the set of all context-free languages. Let $L_1=\emptyset$ and $L_2=\{a^{n^2}\mid n\in \Bbb N\}$. Then $L_1\subset L_2$, $L_1\in \text{CFL}$, $L_2\not\in \text{CFL}$. So, $L_{\text{CFL}}$ is not Turing-recognizable.

$\overline{CF_{TM}}$ is not Turing-recognizable

$\overline{CF_{\text{TM}}}=\{ s : s\text{ is a string that does not encode a TM}\}\sqcup L_{\overline{\text{CFL}}}$, where $\overline{\text{CFL}}$ is the set of all non-context-free formal languages. Let $L_1=\{a^{n^2}\mid n\in \Bbb N\}$ and $L_2=\{a^n\mid n\in \Bbb N\}$. Then $L_1\subset L_2$, $L_1\in \overline{\text{CFL}}$, $L_2\not\in \overline{\text{CFL}}$. So, $L_{\overline{\text{CFL}}}$ is not Turing-recognizable.

Proof of the partial version of the generalized Rice's Theorem

Suppose $L_S$ is recognized by a TM $M_S$. We will construct a TM that recognizes $\overline{HALT_{\text{TM}}}=\{\langle M,w\rangle\mid M\text{ does not halt on }w\}$, which is known as not Turing-recognizable, hence a contradiction. The TM works as follows.

---

On input $\langle M, w\rangle$:

1. Construct a TM $T_{M,w}$ that works as follows:

   On input $x$:

   • Run $M_1$ on $x$, and accept if $M_1$ accepts. Here $M_1$ is a TM that recognizes $L_1$.
   • At the same time, also run $M$ on $w$. If $M$ accepts, run $M_2$ on $x$, and accept if $M_2$ accepts. Here $M_2$ is a TM that recognizes $L_2$.

2. Run $M_S$ on $T_{M,w}$, and accept if $M_S$ accepts.

---

Note this TM accepts $\langle M,w\rangle$ if and only if $M_S$ accepts $\langle T_{M,w}\rangle$, which means $L(T_{M,w})\in S$. Also note

$$L(T_{M,w})=\begin{cases} L_1 & \text{if $M$ does not halt on $w$},\\ L_2 & \text{otherwise}, \end{cases}$$

so the TM accepts $\langle M,w\rangle$ if and only if $M$ does not halt on $w$, which indeed recognizes $\overline{HALT_{\mathrm{TM}}}$.

_{The above proof is a modified version of xskxzr's nice proof of his lemma in his answer.}

Exercises

Exercise 1. Show that a context-free language (that is defined by a context-free grammar) is Turing-recognizable. Show that a non-context-free formal language (that is defined by an unrestricted grammar and that cannot be defined by a context-free grammar) is Turing-recognizable.

Exercise 2. (One minutes or two) Check that both the question and this answer remain valid if we replace "context-free" by "regular".

Exercise 3. Show that $\overline{\text{CFL}}$, the set of all non-context-free formal languages given by their grammars properly encoded by some fixed scheme, is not Turing-recognizable. Hence, $L_{\overline{\text{CFL}}}$ cannot be Turing-recognizable either.

EXercise 3. Read the full version of generalized Rice's Theorem. Can you prove it? (This might not be easy.)

Answer 2

Both of them are unrecognizable by the following lemma:

Lemma. Let $\mathcal{L}$ be a set of languages. If there exists two language $L_1$ and $L_2$ such that:

• $L_1\subseteq L_2$,
• $L_1\in \mathcal{L},L_2\notin\mathcal{L}$, and
• $L_1$ is decidable by a decider $M_1$, $L_2$ is recognizable by a TM $M_2$,

then the language $L=\{\langle M\rangle\mid L(M)\in\mathcal{L}\}$ is unrecognizable.

Proof. Suppose $L$ is recognizable by a TM $M_L$. We will construct a TM that recognizing $\overline{H_{\mathrm{TM}}}=\{\langle M,w\rangle\mid M\text{ does not halt on }w\}$, which is known as unrecognizable, hence a contradiction. The TM works as follows.

On input <M, w>:
    1. Construct a TM N (using M and w) working as follows:
        On input x:
            1. Run M_1 on x, and accept if M_1 accepts
            2. Run M on w
            3. Run M_2 on x, and accept/reject if M_2 accepts/rejects
    2. Run M_L on <N>, and accept/reject if M_L accepts/rejects

Note this TM accepts $\langle M,w\rangle$ if and only if $M_L$ accepts $\langle N\rangle$, which means $L(N)\in\mathcal{L}$. Also note

$$L(N)=\begin{cases} L_2 & \text{if $M$ halts on $w$},\\ L_1 & \text{otherwise}, \end{cases}$$

so the TM accepts $\langle M,w\rangle$ if and only if $M$ does not halt on $w$, which indeed recognizes $\overline{H_{\mathrm{TM}}}$.

---

Now if $\mathcal{L}$ is the set of context free languages, we can choose $L_1=\emptyset$ and $L_2=\{a^nb^nc^n\mid n\ge 0\}$, and using the lemma to show $CF_{TM}=\{\langle M\rangle\mid L(M)\in\mathcal{L}\}$ is unrecognizable. If $\mathcal{L}$ is the set of non-context free languages, we can choose $L_1=\{a^nb^nc^n\mid n\ge 0\}$ and $L_2=\Sigma^*$, and using the lemma to show $\overline{CF_{TM}}$ is unrecognizable.

Answer 3

We can use Rice-Shapiro to prove that both are not recognizable.

Assume $CF_{TM}$ is recognizable. Take any $M$ where $L(M)=\emptyset$. By Rice-Shapiro, since $\langle M \rangle \in CF_{TM}$ we have that every $N$ such that $L(N)\supseteq L(M)=\emptyset$ (which is always true) satisfies $\langle N \rangle \in CF_{TM}$. We reach a contradiction choosing $N$ so that $L(N)$ is not context-free.

Assume $\overline{CF_{TM}}$ is recognizable. Take any $M$ where $L(M)=\{0^n1^n2^n \ | \ n\in\mathbb N\}$ which is not context-free. By Rice-Shapiro, since $\langle M \rangle \in \overline{CF_{TM}}$ there must exist some $N$ such that 1) $L(N)\subseteq L(M)$, 2) $L(N)$ is finite, and 3) $\langle N \rangle \in \overline{CF_{TM}}$. We reach a contradiction since $L(N)$, being finite, is context-free.