# Is there any language that can be Turing-reduced to all languages?

I suppose not, but I do not have a clear way to prove it. Right now, I am trying to find a counter example that there exists a language that cannot be reduced from the language, but I am not sure if there is the right direction.

• Oh sorry, I meant from. Apr 8 '18 at 19:32
• Your edit completely changes the question and invalidates the existing answer, rendering it useless. I'd prefer that you avoid doing that. In this case, now that you've already gotten an answer to your original question, it would be better to ask a new question about the case you meant to ask about. Thanks for your understanding!
– D.W.
Apr 9 '18 at 2:33

Every Turing-decidable language is Turing-reducable to every language.

According to the definition in Wikipedia,

Given two sets $$A,B \subseteq \mathbb{N}$$ of natural numbers, we say $$A$$ is Turing reducible to $$B$$ and write

$$A \leq_T B$$

if there is an oracle machine that computes the characteristic function of $$A$$ when run with oracle $$B$$.

Now if $$A$$ is decidable, the oracle machine can decide $$A$$ even without the use of the oracle, so $$A$$ is Turing-reducible to every language.

• This is almost true. You have to exclude the two trivial languages.
– Raphael
Apr 9 '18 at 5:33
• @Raphael What do you mean? Which trivial case doesn't my answer cover? Apr 9 '18 at 5:46
• The two trivial languages (empty and universal) can't be reduced to in this way. See also those related questions: cs.stackexchange.com/q/7453/98 cs.stackexchange.com/q/19427/98
– Raphael
Apr 9 '18 at 9:24
• @Raphael What you said is many-one reduction, which is a stronger reduction. In the sense of Turing-reduction, I think these trivial languages can also be reduced to according to the definition. Apr 9 '18 at 9:35
• Ah, you're right. We don't need to map inputs; in fact, we can ignore the oracle for $B$ completely. My bad.
– Raphael
Apr 9 '18 at 11:17