3
$\begingroup$

What are some examples of non-enumerable languages whose complement isn't either? I.e., a language L such that L is not Turning-recognizable and L’ is not Turing-recognizable either.

Update: Found some examples:

$\endgroup$
1
  • $\begingroup$ $L_{0,1}=\{\langle M\rangle\mid M\text{ halts on } 0\text{ but not on } 1 \}$ $\endgroup$
    – John L.
    Commented May 5, 2022 at 14:59

1 Answer 1

2
$\begingroup$

A random language is neither recognizable nor co-recognizable almost surely.

Every language which is complete for $\Sigma_k$ or $\Pi_k$, for any $k \geq 2$ (these are classes in the arithmetical hierarchy), is neither recognizable nor co-recognizable. Some examples:

  • The language of all oracle TMs $M$ such that $M$ halts on the empty input when given access to an oracle of the halting problem ($\Sigma_2$-complete).
  • The language of all TMs $M$ such that $M$ halts on finitely many inputs ($\Sigma_2$-complete).
  • The language of all TMs $M$ such that $M$ halts on all inputs ($\Pi_2$-complete).
  • The language of all TMs $M$ such that "$M$ halts on $x$" is decidable ($\Sigma_3$-complete).
  • The language of all TMs $M$ such that $M$ halts on all but finitely many inputs ($\Sigma_3$-complete).

See lecture notes of Terwijn.

$\endgroup$

Your Answer

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

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