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

2more comments