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.

  • $\begingroup$ Oh sorry, I meant from. $\endgroup$
    – Anonny
    Apr 8, 2018 at 19:32
  • 2
    $\begingroup$ 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! $\endgroup$
    – D.W.
    Apr 9, 2018 at 2:33

1 Answer 1


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.

  • $\begingroup$ This is almost true. You have to exclude the two trivial languages. $\endgroup$
    – Raphael
    Apr 9, 2018 at 5:33
  • $\begingroup$ @Raphael What do you mean? Which trivial case doesn't my answer cover? $\endgroup$
    – xskxzr
    Apr 9, 2018 at 5:46
  • $\begingroup$ 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 $\endgroup$
    – Raphael
    Apr 9, 2018 at 9:24
  • $\begingroup$ @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. $\endgroup$
    – xskxzr
    Apr 9, 2018 at 9:35
  • $\begingroup$ Ah, you're right. We don't need to map inputs; in fact, we can ignore the oracle for $B$ completely. My bad. $\endgroup$
    – Raphael
    Apr 9, 2018 at 11:17

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.