Oracle machines that halt on every input

Question

Suppose $x, y \subset \mathbb{N}$ and $x \leq_T y$; that is, there is some oracle machine $e$ such that $n \mapsto \{e\}^y(n)$ is the characteristic function of $x$. (In particular $n \mapsto \{e\}^y(n)$ is total.) Is it always possible to choose $e$ such that additionally, for any $y$', $n \mapsto \{e\}^{y'}(n)$ is total?

Answer 1

No, it is not. Let $T=\{t_0, t_1, t_2, ...\}$ be the set of all total indices - that is, all $e$ such that $\Phi_e^X$ is total for all $X$. (The "$\Phi_e^X$" notation is more commonly used nowadays, and I find it much easier to read.) Now consider the set $$A=\{n: \Phi_{t_n}^T(n)=0\}.$$ We have $A\le_TT$, but clearly no total index witnesses this.

---

Something even stronger is true. For a Turing degree ${\bf d}$, say that $e\in\omega$ is ${\bf d}$-total if for all $X\in{\bf d}$ we have $\Phi_e^X$ is total. For $X\subseteq\omega$, say $e$ is $X$-total if $e$ is $deg(X)$-total. Then we can ask:

If $A\le_TB$, need we always have this witnessed by a $B$-total functional?

Note that the above argument does not address this, and on the face of it this problem seems much harder since the set of $X$-total indices depends on $X$.

However, the answer is still no! Here's a silly proof, via Martin's cone theorem which states that every "nicely definable" set of Turing degrees either contains or is disjoint from a cone (exactly what "nicely definable" means depends on your background set theory, but the Borel case is provable in ZFC alone and is already much more than we need).

Specifically, for $e\in\omega$ let $T_e=\{{\bf d}: e\mbox{ is ${\bf d}$-total}\}$. $T_e$ is clearly Borel (or rather, the set of reals in elements of $T_e$ is Borel), so each $T_e$ contains or is disjoint from a cone. Since the intersection of countably many Turing cones contains again a Turing cone, we have that there is some Turing cone $\mathcal{C}$ satisfying $$\mbox{For all ${\bf d}_0, {\bf d}_1\in$ $\mathcal{C}$ and $e\in\omega$, $e$ is total for ${\bf d}_0$ iff $e$ is total for ${\bf d}_1$.}$$ That is, $\mathcal{C}$ is homogeneous for totality.

Let the set of indices which are total for some (equiv. all) degrees in $\mathcal{C}$ be denoted $\mathcal{T}=\{t_0, t_1, ...\}$. Then since $\mathcal{C}$ is a cone, we can find some set $X\in\mathcal{C}$ with $X\ge_T\mathcal{T}$; now, consider as above the reduction $$\{n: \Phi_{t_n}^X(n)=0\}\le_TX.$$

The point is that even though the set of $X$-total indices seems to depend on $X$, since it's degree-invariant it eventually stabilizes, and then we have sets which compute their own totality predicates. Note that the degree-invariance here is crucial: obviously this same trick fails to give an $X$ which computes $\{e: \Phi_e^X\mbox{ is total}\}$, which in fact always has degree $X''>_TX$. Basically, in a certain sense degree-invariant questions are always "weak": sufficiently powerful reals can answer those questions about themselves.