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
    Commented Feb 13, 2023 at 9:33
  • $\begingroup$ Also RE contains languages, i.e., decision problems. $\endgroup$
    – Steven
    Commented Feb 13, 2023 at 10:42
  • $\begingroup$ Can you further explain please? :) $\endgroup$
    – Geo
    Commented Feb 13, 2023 at 14:54

1 Answer 1


Actually Mapping reduction is the reduction that can do that.

Mapping reduction is defined as A is many reducible to B if there is some computable((recursive))function say f such that For all x, x belongs to A if and only if f(x) belongs to B. It can be proved that in many one reducability if B is r.e, then so is A.


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.