In computability theory, a Turing degree [''X''] is '''low''' if its Turing jump [''X''′] = 0′. A subset <math>S \subset \N </math> is '''low''' if its Turing degree is low.
In other words, <math>X \subset \N </math> is low iff the halting problem for Turing machines equipped with an oracle for <math>X</math> is exactly as difficult as the halting problem for Turing machines without any oracle. Thus, ''X'' being low says that its jump ''X''′ has the least possible degree.
Since every set is computable from its jump, all low set are in 0′, but the jump of sets computable in 0′ can bound any degree recursively enumerable in 0′ (Schoenfield Jump Inversion).
In general, "lowness properties" are properties of sets that can accurately describe how useless they are at being an oracle for Turing machines, usually meaning that its jumps are as low as logically possible. For example: * A degree ''[X]'' is '''low<sub>n</sub>''' iff <math>[X]^{(n)} = 0^{(n)}</math>.<ref>R. Downey, R. A. Shore, [https://www.jstor.org/stable/2275754 Degree Theoretic Definitions of the Low<sub>2</sub> Recursively Enumerable sets]. The Journal of Symbolic Logic Vol. 60, No. 3 (Sep., 1995), p. 728</ref><ref>C. J. Ash, J. Knight, ''Computable Structures and the Hyperarithmetical Hierarchy'' (Studies in Logic and the Foundation of Mathematics, 2000), p. 22</ref> * A set ''X'' is '''generalized low''' if it satisfies <math>[X]' = [X] \or 0'</math>, where <math>\or</math> is the join. * A degree ''[X]'' is '''generalized low<sub>n</sub>''' iff <math>[X]^{(n)} = ([X] \or 0')^{(n-1)}</math>.
The low basis theorem states that any nonempty <math>\Pi^0_1</math> class in <math>2^\omega</math> 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== *High (computability) *Low basis theorem
== References == {{reflist}} * {{cite book | first=Robert I. | last=Soare | title=Recursively enumerable sets and degrees. A study of computable functions and computably generated sets | series=Perspectives in Mathematical Logic | publisher=Springer-Verlag | location=Berlin | year=1987 | isbn=3-540-15299-7 | zbl=0667.03030 }} * {{cite book | last=Nies | first=André | title=Computability and randomness | series=Oxford Logic Guides | volume=51 | location=Oxford | publisher=Oxford University Press | year=2009 | isbn=978-0-19-923076-1 | zbl=1169.03034 }}
Category:Computability theory
{{Mathlogic-stub}}