# Why does many to one reduction imply Turing reducibility?

So, $A\leqslant_mB$ (many to one reduction) means that language $A$ can be reduced to language $B$ if there exists a Turing-calculable function $f$ so $f(A) \subseteq B$ and $f(\overline{A}) \subseteq \overline{B}$.

$A\leqslant_TB$ (Turing reducibility) means that language $A$ can be Turing-reduced to language $B$ if there exists an oracle machine $O^B$ which decides $A$.

I sort of get them both individually, but I don't get why $\leqslant_m$ implies $\leqslant_T$.

• Consider $A \leq_m B$. then you have this Turing-computable function $f$ with that property. Now consider a word $w$. We want to decide whether $w \in A$. But then we can just check whether $f(w) \in B$. That's because if $w \in A$ then we know that $f(w) \in B$ and if $w \notin A$ then we know that $f(w) \notin B$ hence the function $f$ basically is the oracle machine $O^B$ that you need to determine $A \leq_T B$. – Bakuriu Aug 30 '16 at 18:56

To put it informally, $A\leq_{\mathrm{T}}B$ means "If I had a subroutine for $B$, then I could solve $A$", whereas $A\leq_{\mathrm{m}}B$ means, "If I had a subroutine for $B$, then I could solve $A$ using a program that calls the subroutine only once and, furthermore, just returns the answer of the subroutine without doing any further calculation."

If you can solve a problem using a subroutine such that blah blah blah, you can solve that problem using the subroutine.