Turing degrees and enumeration degrees

Question

I'm a bit confused about the difference between Turing degrees and enumeration degrees.

I am unsure whether the Turing reducibility is (or should be) defined only on total functions. In most of the books I checked (e.g. Soare's `Recursively enumerable sets and degrees", Rogers' "Theory of Recursive Functions and effective computability", Shoenfield's "Degree of unsolvability", just to mention some of them) it seems that T-reducibility applies to all functions (partial and total). On the other hand Odifreddi (Classical recursion theory) gives the definition only for total function and says that $\le_T \Rightarrow \le_e$ while the converse does not hold. Moreover Kent, in his PhD thesis, explicitly says that Turing degrees are restricted to total functions and, if we relax this constraint (applying Turing reduction also to partial functions), we obtain the structure of the partial degrees, which is isomorphic to the structure of the enumeration degrees.

Therefore I believe my doubts can be summarized in the following questions: what is the "correct" definition of Turing reducibility? If it is not restricted to total function, then what is the difference between Turing and enumeration degrees?

Answer 1

This definition is the same as given Soare's book "Turing Computability"

Definition. A partial function $f$ is Turing computable in $A$, $f \leq_T A$ if there is an $e$ such that $\Phi_e^A (x) \downarrow=y$ iff $f(x)=y$. A set $B$ is Turing reducible to $A$, $B \leq_T A$, if the characteristic function of $B$ is computable in $A$.

So yes, Turing reducibility is only defined on total functions, as characteristic functions of sets are total.

Cooper [1] defines the degree of a partial function using enumeration degrees.

Definition. Let $f$ be a partial function. Then $$deg(f)=\{g : graph(f) \equiv_e graph(g) \}.$$

An $e$ degree $\mathbf{d}$ is total if there is a total function f with $graph(f)\in \mathbb{d}$. Let $\mathcal{D}, \mathcal{D}_e, \mathcal{P},\mathcal{TOT}$ be the structures of the Turing degrees, enumeration degrees, degrees of partial functions, total enumeration degrees, respectively.

Theorem. $\mathcal{D} \cong \mathcal{TOT}\subseteq \mathcal{D}_e\cong \mathcal{P}$

Sketch of Proof. $\mathcal{D}_e\cong \mathcal{P}$ by $\theta: deg(f)\mapsto deg_e(graph(f))$. The isomorphism between $\mathcal{TOT}$ and $\mathcal D$ is the restriction of $\theta$ to total functions.

For a complete proof and more on that topic see

[1] S. Barry Cooper - Computability theory, 2004. Section 11.3