Editing Turing reduction (section)

== Definition ==

Given two sets <math>A,B \subseteq \mathbb{N}</math> of natural numbers, we say <math>A</math> is '''Turing reducible''' to <math>B</math> and write
:<math>A \leq_T B</math>
[[if and only if]] there is an [[oracle machine]] that computes the [[Indicator function|characteristic function]] of ''A'' when run with oracle ''B''.  In this case, we also say ''A'' is '''''B''-recursive''' and '''''B''-computable'''.

If there is an oracle machine that, when run with oracle ''B'',  computes a [[partial function]] with domain ''A'', then ''A'' is said to be '''''B''-[[recursively enumerable set|recursively enumerable]]''' and '''''B''-computably enumerable'''.

We say <math>A</math> is '''Turing equivalent''' to <math>B</math> and write <math>A \equiv_T B\,</math> if both <math>A \leq_T B</math>  and <math>B \leq_T A.</math> The [[equivalence class]]es of Turing equivalent sets are called '''[[Turing degree]]s'''. The Turing degree of a set <math>X</math> is written <math>\textbf{deg}(X)</math>.

Given a set <math>\mathcal{X} \subseteq \mathcal{P}(\mathbb{N})</math>, a set <math>A \subseteq \mathbb{N}</math> is called '''Turing hard''' for <math>\mathcal{X}</math> if <math>X \leq_T A</math>  for all <math>X \in \mathcal{X}</math>. If additionally <math>A \in \mathcal{X}</math> then <math>A</math> is called '''Turing complete''' for <math>\mathcal{X}</math>.

===Relation of Turing completeness to computational universality===
Turing completeness, as just defined above, corresponds only partially to [[Turing completeness]] in the sense of computational universality.  Specifically, a Turing machine is a [[universal Turing machine]] if its [[halting problem]] (i.e., the set of inputs for which it eventually halts) is [[Many-one reduction|many-one complete]] for the set <math>\mathcal{X}</math> of recursively enumerable sets.  Thus, a necessary ''but insufficient'' condition for a machine to be computationally universal, is that the machine's halting problem be Turing-complete for <math>\mathcal{X}</math>. Insufficient because it may still be the case that, the language accepted by the machine is not itself recursively enumerable.