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 ex ...
, a
Turing degree 'X''is high if it is computable in 0, and the
Turing jump is 0, which is the greatest possible degree in terms of
Turing reducibility for the jump of a set which is computable in 0.
Similarly, a degree is ''high n'' if its n'th jump is the (n+1)'st jump of 0. Even more generally, a degree d is ''generalized high n'' if its n'th jump is the n'th jump of the join of d with 0.
See also
*
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 computabl ...
References
Computability theory
{{mathlogic-stub, date=February 2009