Tell me more ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.
up vote 0 down vote favorite

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?

share|improve this question

2 Answers

up vote 2 down vote

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

share|improve this answer
I'm not quite sure what you mean. Can you perhaps expand a little bit on this? – Aden Dong Oct 17 '12 at 2:42
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. – Yuval Filmus Oct 17 '12 at 4:52
up vote 1 down vote

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).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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