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$
$\endgroup$
2
-
$\begingroup$ Oh sorry, I meant from. $\endgroup$– AnonnyCommented 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. ♦Commented Apr 9, 2018 at 2:33
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
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$– RaphaelCommented Apr 9, 2018 at 5:33
-
$\begingroup$ @Raphael What do you mean? Which trivial case doesn't my answer cover? $\endgroup$– xskxzrCommented 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$– RaphaelCommented 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$– xskxzrCommented 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$– RaphaelCommented Apr 9, 2018 at 11:17