Is being close to a Halting set computable?

Question

Let $\Phi$ be a universal Turing machine and let $S$ be the set on which it halts. I’m curious about if its decidable to check if a number is close to $S$. There are two notions of distance that come to mind: the additive distance and the Hamming distance.

The additive distance, $d_+(x,S)$ is the smallest number $n$ such that at least one of $x+n$ and $x-n$ is in $S$. The Hamming distance, $d_h(x,S)$, is the minimum number of bit flips requires to transform $x$ into an element of $S$. For the purposes of this question, consider numbers as beginning with an infinite string of $0$’s and bits before the first non-zero bit can also be flipped.

These functions can’t be computable because the inverse image of $0$ gives a Halting set. Is it computable to check if $d(x,S)=k$ or if $d(x,S)<k$ for an integer $k\geq 0$?

Does the answer change if we replace $S$ with a different non-computable set? In particular, are these questions always in the same Turing degree as $S$?

Answer 1

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$.

Answer 2

The distribution of numbers in the halting set depends heavily on the specific way you code Turing machines. To get an idea of the problem check out Hamkins and Miasnakov's paper The Halting Probem is Decidable on a Set of Asymptotic Probability One

It's possible to code Turing machines in such a way that every even number is in the halting set S, meaning every x would trivially have $d(x,S) \leq 1$ (in both Hamming and Additive distance), and thus it would be trivially decidable whether $d(x,S) \leq 1$).