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