Skip to main content
deleted 3 characters in body
Source Link
Dan Turetsky
  • 3.1k
  • 16
  • 27

Yes.

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

To ensure nondistinguishabilitydistinguishability, 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 nondistinguishabilitydistinguishability 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.

Yes.

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

To ensure nondistinguishability, 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 nondistinguishability 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.

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.

Source Link
Dan Turetsky
  • 3.1k
  • 16
  • 27

Yes.

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

To ensure nondistinguishability, 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 nondistinguishability 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.