Editing Computability theory (section)

===Other reducibilities===
{{Main|Reduction (recursion theory)}}

An ongoing area of research in computability theory studies reducibility relations other than Turing reducibility. Post<ref name="Post_1944"/> introduced several ''strong reducibilities'', so named because they imply truth-table reducibility. A Turing machine implementing a strong reducibility will compute a total function regardless of which oracle it is presented with. ''Weak reducibilities'' are those where a reduction process may not terminate for all oracles; Turing reducibility is one example.

The strong reducibilities include:
: [[Many-one reduction|One-one reducibility]]: ''A'' is ''one-one reducible'' (or ''1-reducible'') to ''B'' if there is a total computable [[injective function]] ''f'' such that each ''n'' is in ''A'' if and only if ''f''(''n'') is in ''B''.
: [[Many-one reduction|Many-one reducibility]]: This is essentially one-one reducibility without the constraint that ''f'' be injective. ''A'' is ''many-one reducible'' (or ''m-reducible'') to ''B'' if there is a total computable function ''f'' such that each ''n'' is in ''A'' if and only if ''f''(''n'') is in ''B''.
: [[Truth table reduction|Truth-table reducibility]]: ''A'' is truth-table reducible to ''B'' if ''A'' is Turing reducible to ''B'' via an oracle Turing machine that computes a total function regardless of the oracle it is given. Because of compactness of [[Cantor space]], this is equivalent to saying that the reduction presents a single list of questions (depending only on the input) to the oracle simultaneously, and then having seen their answers is able to produce an output without asking additional questions regardless of the oracle's answer to the initial queries. Many variants of truth-table reducibility have also been studied.
Further reducibilities (positive, disjunctive, conjunctive, linear and their weak and bounded versions) are discussed in the article [[Reduction (recursion theory)|Reduction (computability theory)]].

The major research on strong reducibilities has been to compare their theories, both for the class of all computably enumerable sets as well as for the class of all subsets of the natural numbers. Furthermore, the relations between the reducibilities has been studied. For example, it is known that every Turing degree is either a truth-table degree or is the union of infinitely many truth-table degrees.

Reducibilities weaker than Turing reducibility (that is, reducibilities that are implied by Turing reducibility) have also been studied. The most well known are [[arithmetical reducibility]] and [[hyperarithmetical reducibility]]. These reducibilities are closely connected to definability over the standard model of arithmetic.