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

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?

• You have defined $CF_{TM}$, but what is $CF_{TM} \overline{CF_{TM}}$? Is it the concatenation of $CF_{TM}$ and $\overline{CF_{TM}}$? – dkaeae Apr 1 at 8:51
• it is the lack of space, i missed it when i reviewed my post before posting. fixing right now – CrimsonWater Apr 1 at 9:38
• I still don't get it. Should the comma just be an "and"? – dkaeae Apr 1 at 9:41
• is it more understandable now? i tried to fix it using proper spacing. i was asking if any of them are turing recognizable(not their concatenation, but each separately) – CrimsonWater Apr 1 at 9:43
• Aha. Well, what have you tried? Hint: You could use Rice's theorem. – dkaeae Apr 1 at 9:49

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.)

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.

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.