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.

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

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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