1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Oh sorry, I meant from. $\endgroup$ – Anonny Apr 8 '18 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 '18 at 2:33
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This is almost true. You have to exclude the two trivial languages. $\endgroup$ – Raphael Apr 9 '18 at 5:33
  • $\begingroup$ @Raphael What do you mean? Which trivial case doesn't my answer cover? $\endgroup$ – xskxzr Apr 9 '18 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 '18 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 '18 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 '18 at 11:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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