Turing reducibility is the relation 
between sets of integers meaning that an oracle Turing machine with access to 
computes the characteristic
function of 
.
The reduction may make multiple adaptive oracle queries, rather than using a single
many-one transformation. Mutual reducibility defines an equivalence
relation, and its equivalence classes are Turing
degrees. Every computable set is reducible to every oracle, giving the least
degree. The join 
codes the two sets on even and odd integers and represents the least
upper bound of their degrees.
Turing Reducibility
See also
Characteristic Function, Computable Number, Turing Degree, Turing MachineExplore with Wolfram|Alpha
References
Slaman, T. A. "Global Properties of the Turing Degrees and the Turing Jump." In Computational Prospects of Infinity. Part I. Tutorials (Ed. C. Chong, Q. Feng, T. A. Slaman, W. H. Woodin, and Y. Yang). Hackensack, NJ: World Scientific, pp. 83-101, 2008. https://doi.org/10.1142/9789812794055_0002.Soare, R. I. Turing Computability: Theory and Applications. Berlin, Germany: Springer, 2016. https://doi.org/10.1007/978-3-642-31933-4.Cite this as:
Weisstein, Eric W. "Turing Reducibility." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/TuringReducibility.html