High (computability)
Encyclopedia
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′.
Computability theory
Computability theory, also called recursion theory, is a branch of mathematical logic that originated in the 1930s with the study of computable functions and Turing degrees. The field has grown to include the study of generalized computability and definability...
, a Turing degree
Turing degree
In computer science and mathematical logic the Turing degree or degree of unsolvability of a set of natural numbers measures the level of algorithmic unsolvability of the set...
[X] is high if it is computable in 0′, and the Turing jump
Turing jump
In computability theory, the Turing jump or Turing jump operator, named for Alan Turing, is an operation that assigns to each decision problem a successively harder decision problem with the property that is not decidable by an oracle machine with an oracle for .The operator is called a 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′.