is that the machine's halting problem be Turing-complete for the set of recursively enumerable sets. Insufficient because it may still be the case that, the language accepted by the machine is not itself recursively enumerable. Example Let denote the set of input values for which the Turing machine with index e halts. Then the sets and are Turing equivalent (here denotes an effective pairing function). A reduction showing can be constructed using the fact that . Given a pair , a new index can be constructed using the smn theorem such that the program coded by ignores its input and merely simulates the computation of the machine with index e on input n. In particular, the machine with index either halts on every input or halts on no input. Thus holds for all e and n. Because the function i is computable, this shows . The reductions presented here are not only Turing reductions but many-one reductions, discussed below. 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 is transitive: if and then . Moreover, holds for every set A, and thus the relation is a preorder (it is not a partial order because and does not necessarily imply ). There are pairs of sets such that A is not Turing reducible to B and B is not Turing reducible to A. Thus is not a total order. There are infinite decreasing sequences of sets under . 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. The use of a reduction Since every reduction from a set to a set has to determine whether a single element is in in only finitely many steps, it can only make finitely many queries of membership in the set . When the amount of information about the set used to compute a single bit of is discussed, this is made precise by the use function. Formally, the use of a reduction is the function that sends each natural number to the largest natural number whose membership in the set B was queried by the reduction while