A set is Turing-reducible to when an oracle machine with membership oracle computes the characteristic function of . Unlike a many-one reduction, it may make adaptive queries and reverse or combine oracle answers.
Build an infinite oracle as an increasing union of finite binary strings. With the diagonal halting set as an oracle, decide whether some finite extension makes a specified Turing functional halt with a binary output at a fresh input. In a yes case, preserve that finite computation and commit the opposing set's bit to the opposite value. In a no case, no subsequent infinite extension can yield a characteristic-function value there. Length growth makes the resulting sets computable in the halting oracle.
A Turing functional is a partial computation performed by an oracle machine, viewed as a function of both the oracle and input . Oracle programs admit an effective enumeration. Every convergent computation inspects only a finite part of its oracle, recorded by its oracle use.
The use of a convergent oracle computation is one more than its largest queried position, or zero if there are no queries. Preserving the oracle below this number preserves the computation. This finite dependence supplies the restraints in a finite-injury priority construction.
The Turing degree of a set is its equivalence class under mutual Turing reducibility. Degrees inherit the partial order induced by Turing reducibility. The Friedberg–Muchnik theorem gives incomparable degrees represented by computably enumerable sets.
There are incomparable Turing degrees strictly between the computable degree and the degree of the diagonal halting set. An oracle-assisted finite-extension construction alternately defeats each Turing functional in the two directions. Since the sets are computable in the halting oracle, their degrees are at most ; incomparability makes them nonzero and strictly below . This theorem does not require the constructed sets to be computably enumerable. The Friedberg–Muchnik theorem supplies that stronger conclusion.
Post problem asks whether a computably enumerable set can have a Turing degree strictly between the computable degree and the degree of the halting problem. The Friedberg–Muchnik theorem answers yes by constructing two incomparable computably enumerable degrees.
Articles by others on the same topic
In computational theory, a Turing reduction is a method used to compare the relative difficulty of computational problems. Specifically, a problem \( A \) is Turing reducible to a problem \( B \) if there exists a Turing machine that can solve \( A \) using an oracle that solves \( B \). This means that the Turing machine can ask the oracle questions about problem \( B \) and use the answers to help solve problem \( A \).