High (computability)
Jump to navigation
Jump to search
This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages)
|
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′.[1]
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. I. (1987). Recursively enumerable sets and degrees : a study of computable functions and computably generated sets. Berlin: Springer-Verlag. p. 71. ISBN 3-540-15299-7.
Categories:
- Articles with topics of unclear notability from November 2021
- All articles with topics of unclear notability
- Wikipedia articles that are too technical from November 2021
- All articles that are too technical
- Articles with multiple maintenance issues
- Computability theory
- All stub articles
- Mathematical logic stubs