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.

equivalentto $WKL_0$ for trivial reasons: $REC$ is a model! $\endgroup$ – Noah Schweber Jun 8 '16 at 1:45