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.

  • $\begingroup$ Note that "Every distinguishable set is computable" can't be equivalent to $WKL_0$ for trivial reasons: $REC$ is a model! $\endgroup$ Jun 8, 2016 at 1:45

2 Answers 2



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.


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.

  • $\begingroup$ +1 and good question! On the face of it, I appear to need actual $WKL_0$ - see my answer linked in the question. However, it isn't clear to me that I can't improve this to get away with just a $PA$ degree. I'll think more on it. $\endgroup$ Jun 14, 2016 at 5:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.