A Turing degree is an equivalence class of sets of integers under mutual Turing reducibility.
The ordering of degrees is induced by reducibility and is a partial
order with a least element, the degree of computable sets. The join of two degrees
is represented by the oracle join of their sets. This orders computational information
rather than time or space complexity.
The rigidity conjecture asks whether every order automorphism of the full degree structure is the identity.
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.
