Low (computability)

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′.

See also

• High (computability)

• Low Basis Theorem

References

• 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. Vol. 51. Oxford: Oxford University Press. ISBN 978-0-19-923076-1. Zbl 1169.03034.