Skip to main content
added 355 characters in body
Source Link
Andrej Bauer
  • 48.8k
  • 11
  • 131
  • 239

Let me make James's answer a bit more explicit to show how the answer depends on the coding of Turing machines. I will work with the additive distance.

As James pointed out, we can make sure that the halting set is very dense, for instance by having every even number encode a fixed machine that halts. This way the question $d(x,H) \geq k$ and $d(x, H) = k$ become decidable in $x$, for all $k \geq 2$. We cannot do better than this, for decidability of $d(x, H) \geq 1$ implies decidability of the halting set $H$.

We can also make sure that the halting set is sparse, for instance make sure that any number which is not a multiple of $k + 1$ encodes a non-halting machine. In such a case $d(x, H) = k$ cannot be decidable in $x$ for any $k$: if we can decide $d(m \cdot (k+1), H) = k$ then we can tell whether $m \cdot (k+1)$ halts, as it is the only candidate for a halting machine which is within distance $k$ from $m \cdot (k+1)$.

Now let us consider the question in general for any non-decidable set $S$, not necessarily the halting set. If we replace $S$ with $\{2 \cdot s \mid s \in S\} \cup \{2 \cdot n + 1 \mid n \in \mathbb{N}\}$ or $\{s \cdot (k+1) \mid s \in S\}$ then the Turning degree of $S$ does not change and we can apply the previous reasoning.

So the answer depends entirely on the coding and is not invariant with respect to the Turing degree of the set under consideration.

Supplemental: We can make the set so sparse that it works for all $k$ at once. Given a non-decidable set $S$, consider the set $$T = \{s^2 \mid s \in S\}.$$ For all $k \in \mathbb{N}$ and sufficiently large $x$, $d(x, T) = k$ is equivalent to $x \in S$. Therefore $d(x, T) = k$ cannot be decidable in $x$.

Let me make James's answer a bit more explicit to show how the answer depends on the coding of Turing machines.

As James pointed out, we can make sure that the halting set is very dense, for instance by having every even number encode a fixed machine that halts. This way the question $d(x,H) \geq k$ and $d(x, H) = k$ become decidable in $x$, for all $k \geq 2$. We cannot do better than this, for decidability of $d(x, H) \geq 1$ implies decidability of the halting set $H$.

We can also make sure that the halting set is sparse, for instance make sure that any number which is not a multiple of $k + 1$ encodes a non-halting machine. In such a case $d(x, H) = k$ cannot be decidable in $x$ for any $k$: if we can decide $d(m \cdot (k+1), H) = k$ then we can tell whether $m \cdot (k+1)$ halts, as it is the only candidate for a halting machine which is within distance $k$ from $m \cdot (k+1)$.

Now let us consider the question in general for any non-decidable set $S$, not necessarily the halting set. If we replace $S$ with $\{2 \cdot s \mid s \in S\} \cup \{2 \cdot n + 1 \mid n \in \mathbb{N}\}$ or $\{s \cdot (k+1) \mid s \in S\}$ then the Turning degree of $S$ does not change and we can apply the previous reasoning.

So the answer depends entirely on the coding and is not invariant with respect to the Turing degree of the set under consideration.

Let me make James's answer a bit more explicit to show how the answer depends on the coding of Turing machines. I will work with the additive distance.

As James pointed out, we can make sure that the halting set is very dense, for instance by having every even number encode a fixed machine that halts. This way the question $d(x,H) \geq k$ and $d(x, H) = k$ become decidable in $x$, for all $k \geq 2$. We cannot do better than this, for decidability of $d(x, H) \geq 1$ implies decidability of the halting set $H$.

We can also make sure that the halting set is sparse, for instance make sure that any number which is not a multiple of $k + 1$ encodes a non-halting machine. In such a case $d(x, H) = k$ cannot be decidable in $x$ for any $k$: if we can decide $d(m \cdot (k+1), H) = k$ then we can tell whether $m \cdot (k+1)$ halts, as it is the only candidate for a halting machine which is within distance $k$ from $m \cdot (k+1)$.

Now let us consider the question in general for any non-decidable set $S$, not necessarily the halting set. If we replace $S$ with $\{2 \cdot s \mid s \in S\} \cup \{2 \cdot n + 1 \mid n \in \mathbb{N}\}$ or $\{s \cdot (k+1) \mid s \in S\}$ then the Turning degree of $S$ does not change and we can apply the previous reasoning.

So the answer depends entirely on the coding and is not invariant with respect to the Turing degree of the set under consideration.

Supplemental: We can make the set so sparse that it works for all $k$ at once. Given a non-decidable set $S$, consider the set $$T = \{s^2 \mid s \in S\}.$$ For all $k \in \mathbb{N}$ and sufficiently large $x$, $d(x, T) = k$ is equivalent to $x \in S$. Therefore $d(x, T) = k$ cannot be decidable in $x$.

Source Link
Andrej Bauer
  • 48.8k
  • 11
  • 131
  • 239

Let me make James's answer a bit more explicit to show how the answer depends on the coding of Turing machines.

As James pointed out, we can make sure that the halting set is very dense, for instance by having every even number encode a fixed machine that halts. This way the question $d(x,H) \geq k$ and $d(x, H) = k$ become decidable in $x$, for all $k \geq 2$. We cannot do better than this, for decidability of $d(x, H) \geq 1$ implies decidability of the halting set $H$.

We can also make sure that the halting set is sparse, for instance make sure that any number which is not a multiple of $k + 1$ encodes a non-halting machine. In such a case $d(x, H) = k$ cannot be decidable in $x$ for any $k$: if we can decide $d(m \cdot (k+1), H) = k$ then we can tell whether $m \cdot (k+1)$ halts, as it is the only candidate for a halting machine which is within distance $k$ from $m \cdot (k+1)$.

Now let us consider the question in general for any non-decidable set $S$, not necessarily the halting set. If we replace $S$ with $\{2 \cdot s \mid s \in S\} \cup \{2 \cdot n + 1 \mid n \in \mathbb{N}\}$ or $\{s \cdot (k+1) \mid s \in S\}$ then the Turning degree of $S$ does not change and we can apply the previous reasoning.

So the answer depends entirely on the coding and is not invariant with respect to the Turing degree of the set under consideration.