Low (computability)

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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[edit]