1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – xavierm02 Sep 25 '16 at 0:04
  • 1
    $\begingroup$ You might want to read about the Turing Jump. $\endgroup$ – xavierm02 Sep 25 '16 at 0:06
  • $\begingroup$ There's also the uniform halting problem, and termination of a rewriting system. $\endgroup$ – xavierm02 Sep 25 '16 at 0:09
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.