In computability theory, a Turing degree [X] is low if the Turing jump [X′] is 0′, which is the least possible degree in terms of Turing reducibility for the jump of a set. Since every set is computable from its jump, any low set is computable in 0′. A set is low if it has low degree.
More generally, a set X is generalized low if it satisfies X′ ≡T X + 0′.
- Soare, Robert I. (1987). Recursively enumerable sets and degrees. A study of computable functions and computably generated sets. Perspectives in Mathematical Logic. Berlin: Springer-Verlag. ISBN 3-540-15299-7. Zbl 0667.03030.
- Nies, André (2009). Computability and randomness. Oxford Logic Guides 51. Oxford: Oxford University Press. ISBN 978-0-19-923076-1. Zbl 1169.03034.
|This mathematical logic-related article is a stub. You can help Wikipedia by expanding it.|