High (computability)
In computability theory, a Turing degree [X] is high if it is computable in 0′, and the Turing jump [X′] is 0′′, which is the greatest possible degree in terms of Turing reducibility for the jump of a set which is computable in 0′ (Soare 1987:71).
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
References
Soare, R. Recursively enumerable sets and degrees. Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1987. ISBN 3-540-15299-7
This article is issued from Wikipedia - version of the 9/17/2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.