High (computability)
From HandWiki - Reading time: 1 min
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.
 |  |
Licensed under CC BY-SA 3.0 | Source: https://handwiki.org/wiki/High_(computability)2 views | ↧ Download this article as ZWI file
EncycloReader
is supported by the 
KSF