Low (computability)

In computability theory, a Turing degree [X] is low if the Turing jump [X] is 0. A set is low if it has low degree. Since every set is computable from its jump, any low set is computable in 0, but the jump of sets computable in 0 can bound any degree r.e. in 0 (Schoenfield Jump Inversion). X being low says that its jump X has the least possible degree in terms of Turing reducibility for the jump of a set.

A degree is low n if its n'th jump is the n'th jump of 0. A set X is generalized low if it satisfies XT X + 0, that is: if its jump has the lowest degree possible. And a degree d is generalized low n if its n'th jump is the (n-1)'st jump of the join of d with 0. More generally, properties of sets which describe their being computationally weak (when used as a Turing oracle) are referred to under the umbrella term lowness properties.

By the Low basis theorem of Jockusch and Soare, any nonempty \Pi^0_1 class in 2^\omega contains a set of low degree. This implies that, although low sets are computationally weak, they can still accomplish such feats as computing a completion of Peano Arithmetic. In practice, this allows a restriction on the computational power of objects needed for recursion theoretic constructions: for example, those used in the analyzing the proof-theoretic strength of Ramsey's theorem.

See also

References


    This article is issued from Wikipedia - version of the Thursday, March 24, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.