Turing Degree

A Turing degree is an equivalence class of sets of natural numbers, or equivalently of decision problems, gathered together according to Turing reducibility, the relation that holds between two sets when a computing device given access to one set as an oracle can decide membership in the other, so that any two sets in the same degree are exactly as computationally hard as one another. The underlying notion of computation by an oracle machine traces back to the British mathematician Alan Turing's foundational 1936 work establishing the modern theory of computability, and the systematic study of the degrees themselves as a mathematical structure was developed soon after by the American mathematician Emil Post. The Turing degrees form a partially ordered structure under reducibility, with the degree of the computable sets sitting at the very bottom, and the degree of the halting problem, often written as zero prime, standing as a canonical example of a set that is well defined but not computable. The structure of the Turing degrees, including which patterns of order and complexity can and cannot occur within it, remains an active area of research in computability theory.