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!

  • $\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


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.