Misplaced Pages

This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these messages) The topic of this article may not meet Misplaced Pages's general notability guideline. Please help to demonstrate the notability of the topic by citing reliable secondary sources that are independent of the topic and provide significant coverage of it beyond a mere trivial mention. If notability cannot be shown, the article is likely to be merged, redirected, or deleted. Find sources: "High" computability – news · newspapers · books · scholar · JSTOR (November 2021) (Learn how and when to remove this message) This article may be too technical for most readers to understand. Please help improve it to make it understandable to non-experts, without removing the technical details. (November 2021) (Learn how and when to remove this message) (Learn how and when to remove this message)

In computability theory, a Turing degree 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)

References

1. 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.

This mathematical logic-related article is a stub. You can help Misplaced Pages by expanding it.

• v
• t
• e

• Computability theory
• Mathematical logic stubs