Editing Turing reduction (section)

== Properties ==

* Every set is Turing equivalent to its complement.
* Every [[computable set]] is Turing reducible to every other set.  Because any computable set can be computed with no oracle, it can be computed by an oracle machine that ignores the given oracle.
* The relation <math>\leq_T</math> is transitive: if <math>A \leq_T B</math> and <math>B \leq_T C</math> then <math>A \leq_T C</math>.  Moreover, <math>A \leq_T A</math> holds for every set ''A'', and thus the relation <math>\leq_T</math> is a [[preorder]] (it is not a [[partial order]] because <math>A \leq_T B</math> and <math>B \leq_T A </math> does not necessarily imply <math>A = B</math>).
* There are pairs of sets <math>(A,B)</math>  such that ''A'' is not Turing reducible to ''B'' and ''B'' is not Turing reducible to ''A''.  Thus <math>\leq_T</math> is not a [[total order]].
* There are infinite decreasing sequences of sets under <math>\leq_T</math>. Thus this relation is not [[well-founded]].
* Every set is Turing reducible to its own [[Turing jump]], but the Turing jump of a set is never Turing reducible to the original set.