Can noncomputable sets be distinguishable in $RCA_0$?

Question

Say that a set $X\subseteq\omega$ is distinguishable if there is some Turing machine $\Phi_e$ which, when given two sets exactly one of which is $X$, can determine which set is $X$. Formally, $X$ is distinguishable if there is some Turing machine $\Phi_e$ such that for all $Y\not=X$, $$\Phi_e^{X\oplus Y}(0)=0,\quad \Phi_e^{Y\oplus X}(0)=1.$$ (Think of "$0$" and "$1$" as meaning "Left" and "Right.")

Clearly every computable set is distinguishable; it is not hard to show (see my answer to https://math.stackexchange.com/questions/1189370/is-there-a-turing-machine-that-can-distinguish-the-halting-problem-among-others) that the converse also holds. My question is about the reverse mathematics of the converse. Specifically, my proof used Weak Konig's Lemma, and I don't immediately see a way to do without it. So my question is:

Is it consistent with $RCA_0$ that there is a non-computable, distinguishable set?

---

Motivation: Over the last year or so I've developed an interest in "alternate computability theories" - e.g. see Visser's delightfully-named paper "Oracle bites theory" at http://www.phil.uu.nl/preprints/lgps/authors/visser/oracle-bites-theory/pdf. I'm especially interested in "almost computable" sets in such theories, and distinguishable sets might provide such an example.

Answer 1

Yes.

Claim. There is a noncomputable $\Delta^0_2$ set $X$ which is distinguishable from every set it computes.

To ensure distinguishability, we must create a machine $\Phi$ such that for every functional $\Psi_e$ with $\Psi_e^X$ total and $\Psi_e^X \neq X$, there is a pair $(\sigma, \tau)$ with $\sigma \prec X$, $\tau = \Psi_e^\sigma$, $\tau \neq \sigma$, $\Phi^{\sigma\oplus\tau}(0) = 0$ and $\Phi^{\tau\oplus\sigma}(0) = 1$. So we have a requirement for every $e$, and we wait until we see a pair $(\sigma, \tau)$ that we like and then enumerate such axioms into $\Phi$. But when we enumerate the axioms, we are forever denying the possibility that $\tau$ will be an initial segment of $X$. And we will need to occasionally change $X$ to ensure noncomputability.

So we simply arrange that the $\tau$ are chosen long, so that $\sum_{(\sigma, \tau)} 2^{-|\tau|}$ is small. Then there will always be strings available to change to. Now arrange the above distinguishability requirements into a finite injury construction along with standard noncomputability requirements.

I suspect that with some care, this could be modified to make $X$ c.e..

Now consider the model of $RCA_0$ $(\omega, \{Y : Y \le_T X\})$. This has a distinguishable, noncomputable set.

Answer 2

Extending D. Turetsky's answer: If $\mathcal{M}$ is a Turing ideal containing no PA degree, then every $\Delta_2$ degree in $\mathcal{M}$ contains a set that is computably distinguishable within $\mathcal{M}$.

Lemma. If $\mathcal{M}$ contains no PA degree, then $\mathcal{M}$'s version of the Cantor space $2^\omega$ is computably homeomorphic to $\mathcal{M}$'s version of the Baire space $\omega^\omega$.

Proof. Fix a computable binary tree with no path, and name its leaf nodes $\tau_1,\tau_2,\ldots$. Every $f \in 2^\omega$ is a concatenation of infinitely many $\tau_{n_1}\tau_{n_2}\cdots$ and through this maps to the string $n_1n_2\cdots \in \omega^\omega$.

Proof of main claim. Fix a $\Delta_2$ set $D$ in $\mathcal{M}$. Construct a computable tree $T \subseteq \omega^{<\omega}$ whose unique path $P$ is $D$'s computation function, i.e., the map taking $n$ to the least $s$ for which $D_s\cap[0,n] = D \cap [0,n]$. Transform $T$ using the Lemma into a computable $T^* \subseteq 2^{<\omega}$. Then $T^*$ has a unique path $P^* \equiv_T P \equiv_T D$, and this $P^*$ is distinguishable by the procedure which takes $X,Y$ and checks to see if their initial segments are all in $T^*$. $\square$

I'd be curious to know whether your proof of distinguishable-equals-computable really needs $WKL$ in the form of a $PA(X)$ degree, or whether it can be finessed down to a $PA$. It would narrow the gap if you're looking for a reversal.