4
$\begingroup$

As the title suggests. Also, such a language must satisfy that neither it nor its complement are semi-decidable. I already know that $All_{TM}, EQ_{TM}, T$ (that is the set of all deciders) satisfy this property. But I tried reducing these to their complements directly, and via some sort of intermediate language, but to no avail. Can anyone help?

$\endgroup$

2 Answers 2

3
$\begingroup$

Try the following construction. Given a language $L$, use $$ \{0x : x \notin L\} \cup \{1x : x \in L\}. $$

$\endgroup$
2
  • $\begingroup$ I'm not quite sure what you mean. Can you perhaps expand a little bit on this? $\endgroup$
    – Aden Dong
    Oct 17, 2012 at 2:42
  • 1
    $\begingroup$ Consider all possible words. Prefix those which belong to $L$ by $1$, those that don't by $0$. This may be relevant to your question. $\endgroup$ Oct 17, 2012 at 4:52
2
$\begingroup$

Another more advanced answer is to look at a complete problem from a class that is closed under complement. For example, take the arithmetical hierarchy which is closed under complements. Now consider a complete problem for it like:

Given: a sentence in the language of first-order arithmetic,
Question: is the sentence true (in the standard model $\mathbb{N}$)?

It is easy that one can reduce this to its complement by negating the sentence.

This works generally for any class that is closed under completion and has a complete problem (w.r.t. many-one reductions).

$\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.