Low (computability)

From Wikipedia, the free encyclopedia

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

[edit] See also

• High (computability)

• Low Basis Theorem

[edit] References

Soare, R. Recursively enumerable sets and degrees. Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1987. ISBN 3-540-15299-7