# Example of a language that is neither recognizable nor co-recognizable?

Is there an example of a language that is neither recognizable nor co-recognizable?

A relevant (easy) theorem is that a language is decidable iff it is recognizable and co-recognizable.

An example of an undecidable language is the set "acceptance problem," i.e. the set of strings (Turing Machine = M, string = s) such that M accepts s. It is recognizable and not co-recognizable.

A less "constructive" proof that there exist unrecognizable languages is that there are uncountably many languages and countably many TMs. I believe this also establishes the existence of languages that are not recognizable or co-recognizable.

Is there an "example" of such a language?

I put "constructive" and "example" in quotes because I suspect I am creating a meta-logical contradiction, whereby stripping a language of recognizability and co-recognizability also strips it of the forms of describability that might intuitively constitute a "construction" or "description." I am interested in any results that make rigorous how to "talk" about languages that are not recognizable or co-recognizable, or any hardness results on doing so.

• Yes. Take $L_1\in RE\setminus R$ over $\Sigma=\{0,1\}$. Then let $L_2=0L_1\sqcup 1\overline{L_1}$. If $L_2$ was $RE$, then by enumerating its elements and keeping only those starting with $0$ (resp. with $1$), you would have an algorithm enumerating elements of $L_1$ (resp. $\overline{L_1}$). So you would have $L_1\in RE$ and $\overline{L_1}\in RE$ so that $L_1\in R$, which we assumed to be false. – xavierm02 Sep 25 '16 at 0:04
• You might want to read about the Turing Jump. – xavierm02 Sep 25 '16 at 0:06
• There's also the uniform halting problem, and termination of a rewriting system. – xavierm02 Sep 25 '16 at 0:09

The language TOT of all Turing machines halting on all inputs is $\Pi_2$-complete, and so is neither recognizable nor co-recognizable. You can find more examples if you search for material on the arithmetical hierarchy. Anything beyond $\Sigma_1$ and $\Pi_1$ will fit your bill.