We formalized the intuitive notion of a reduction that we saw in lecture with the definition of a mapping reduction. However, there are other ways to formalize the idea of reductions. One formalization, called a Turing reduction, captures the intuition that in a reduction from A to B,a decider for A can be implemented by calling, possibly more than once, a decider for B as a subroutine. An algorithm with access to a subroutine for deciding B is formalized by the definition of an oracle Turing machine. Prove that if there is a mapping reduction from A to B, then there is a Turing reduction from A to B.
