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



Is being close to a Halting set computable?
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$.


