The jump is definable in the structure of the degrees of unsolvability
S. Barry Cooper · Bulletin of the American Mathematical Society · 1990
Recursion theory deals with computability on the natural numbers.A function ƒ from N to N is computable (or recursive) if it can be calculated by some program on a Turing machine, or equivalently on any other general purpose computer.A major topic of interest, introduced in Post [23], is the notion of relative difficulty of computation.A function ƒ is computable relative to a function g if after equipping the machine with a black box subroutine that provides the values of g, there is a program (which now may call g via the subroutine) which computes ƒ.In this case we write ƒ < T g.Two functions are Turing equivalent if each is computable relative to the other; the equivalence classes are called Turing degrees.These degrees form a partial ordering 3 under the induced reducibility relation < .The structural analysis of the partial ordering 3 has been a major area of research in recursion theory since the pioneering paper of Kleene and Post [14].Kleene and Post proved a number of results on the structure of 3 including the embeddability of arbitrary countable partial orders into 3, and obtained partial results on extendability of a given embedding to a larger domain.This line of investigation was pursued by many people over the next twenty-five years, culminating in essentially complete solutions of these problems, and a characterization of the possible ideals of the structure 3 (see Lachlan and Lebeuf [16] and Lerman [17],[18]).Kleene and Post also considered the enriched structure 3 1 equipped with the "jump operator", denoted ', which is a canonical operation on degrees which takes each degree d to a strictly