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?
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
Try the following construction. Given a language $L$, use $$ \{0x : x \notin L\} \cup \{1x : x \in L\}. $$
answered Oct 16, 2012 at 5:22
-
$\begingroup$ I'm not quite sure what you mean. Can you perhaps expand a little bit on this? $\endgroup$ Commented 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$ Commented Oct 17, 2012 at 4:52
$\begingroup$
$\endgroup$
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).
