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. 



Can noncomputable sets be distinguishable in $RCA_0$?
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.


