Turing degree

Turing degree, also called degree of unsolvability, is a concept in computer science and mathematical logic that measures the level of algorithmic unsolvability of a set of natural numbers. It is fundamental in computability theory, where sets of natural numbers are often regarded as decision problems. The Turing degree of a set indicates how difficult it is to solve the associated decision problem.

Two sets are considered Turing equivalent if they share the same level of unsolvability, and each Turing degree is a collection of all sets that are Turing equivalent to one another. Consequently, sets belong to different degrees precisely when they are not Turing equivalent. The degrees are partially ordered: if the degree of a set X is less than that of a set Y, then any procedure that correctly decides membership in Y can be effectively converted into a procedure that decides membership in X, even if those procedures are not computable. This ordering formalizes the notion of relative algorithmic unsolvability.

The concept was introduced by Alan Turing, and many foundational results were established by subsequent researchers, leading to intense ongoing study. A key proof technique in this area is the priority method. Every Turing degree is countably infinite, and there are uncountably many distinct degrees.

Turing equivalence

For any degree a, the strict inequality a < a′ holds, where a′ is the Turing jump of a. The degrees form a join-semilattice under the operation of least upper bound, but they do not form a lattice, as some pairs of degrees lack a greatest lower bound. A unique degree, denoted 0, contains all computable sets and is the least element of the entire partial order. The degree 0′ is the degree of the halting problem.

Emil Post investigated the recursively enumerable (r.e.) degrees and posed the question of whether an r.e. degree exists strictly between 0 and 0′. This became known as Post's problem, and it was solved independently by Friedberg and Muchnik, who demonstrated that such intermediate r.e. degrees do exist. Their proofs introduced the priority method, which has since become the primary technique for establishing results about r.e. sets.