In
computability theory
Computability theory, also known as recursion theory, is a branch of mathematical logic, computer science, and the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees. The field has since e ...
, a
Turing degree
In computer science and mathematical logic the Turing degree (named after Alan Turing) or degree of unsolvability of a set of natural numbers measures the level of algorithmic unsolvability of the set.
Overview
The concept of Turing degree is fund ...
'X''is low if the
Turing jump
In computability theory, the Turing jump or Turing jump operator, named for Alan Turing, is an operation that assigns to each decision problem a successively harder decision problem with the property that is not decidable by an oracle machine w ...
'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
In computability theory, a Turing reduction from a decision problem A to a decision problem B is an oracle machine which decides problem A given an oracle for B (Rogers 1967, Soare 1987). It can be understood as an algorithm that could be used to ...
for the jump of a set.
There are various related properties to low degrees:
* A degree is ''low
n'' if its n'th jump is the n'th jump of 0.
[C. J. Ash, J. Knight, ''Computable Structures and the Hyperarithmetical Hierarchy'' (Studies in Logic and the Foundation of Mathematics, 2000), p. 22]
* A set ''X'' is ''generalized low'' if it satisfies ''X''′ ≡
T ''X'' + 0′, that is: if its jump has the lowest degree possible.
* 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 The low basis theorem is one of several basis theorems in computability theory, each of which showing that, given an infinite subtree of the binary tree 2^, it is possible to find an infinite path through the tree with particular computability prop ...
of Jockusch and Soare, any nonempty
class in
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
In proof theory, ordinal analysis assigns ordinals (often large countable ordinals) to mathematical theories as a measure of their strength.
If theories have the same proof-theoretic ordinal they are often equiconsistent, and if one theory h ...
of
Ramsey's theorem
In combinatorics, Ramsey's theorem, in one of its graph-theoretic forms, states that one will find monochromatic cliques in any edge labelling (with colours) of a sufficiently large complete graph. To demonstrate the theorem for two colours (say ...
.
See also
*
High (computability)
*
Low Basis Theorem The low basis theorem is one of several basis theorems in computability theory, each of which showing that, given an infinite subtree of the binary tree 2^, it is possible to find an infinite path through the tree with particular computability prop ...
References
*
*
Computability theory
{{Mathlogic-stub