0
$\begingroup$

I know that if there is a Turing Reduction from $A$ to $B$, say $A \le_T B$, and $B \in R$ then $A \in R$.

I also know that Turing Reduction is for Decision, and not Recognition.

Is it possible to design a new type of reduction, such that if $B \in RE$ then $A \in RE$ ?

Thank you!

Improve this question
$\endgroup$
3
  • $\begingroup$ To my knowledge, many-one reduction does that. $\endgroup$
    – Nathaniel
    Feb 13 at 9:33
  • $\begingroup$ Also RE contains languages, i.e., decision problems. $\endgroup$
    – Steven
    Feb 13 at 10:42
  • $\begingroup$ Can you further explain please? :) $\endgroup$
    – Geo
    Feb 13 at 14:54

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.