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

  • $\begingroup$ You can compute an upper bound on the distance, if there is one. Determining if the distance is 0 is the same as the Halting problem. I forget the complexity of deciding which machines halt on any input, but Soare's classic R.E. text should have it. Gerhard "Guesses It's Pi Zero Three" Paseman, 2018.10.05. $\endgroup$ Oct 6 '18 at 4:10
  • $\begingroup$ @GerhardPaseman How would I compute an upper bound on the distance? I’m not sure what you mean by “if there is one,” but $d_+$ is bounded by the larger of $x$ and the smallest element of $S$. The issue is that knowing what the smallest element of $S$ is seems hard. $\endgroup$ Oct 6 '18 at 4:22
  • $\begingroup$ The point is to do computations in parallel on all inputs, and shift computation when you find an element in S. This gives an upper bound between x and S, assuming S is nonempty. Then you can decide to look for members of S closer to x or not. However, in general you can't decide if x is in S, nor can you compute the precise distance. For those machines for which S is empty, this method does not terminate, and you can't compute which machines those are. Gerhard "Assuming No Oracles Are Available" Paseman, 2018.10.05. $\endgroup$ Oct 6 '18 at 4:31
  • $\begingroup$ Suppose M simply ignores its input, and when you start it running, it begins searching for a proof of the Riemann hypothesis and halts if it finds one. Since we don't know whether RH is provable, either M halts on every input or it halts on no inputs, but we don't know which. Thus, for given x, there's not a useful bound on the distance from x to the nearest member of the halting set. (I think you wanted Φ to be a specific machine rather than a universal one). $\endgroup$
    – none
    Oct 6 '18 at 5:20
  • 2
    $\begingroup$ @none: It does not matter what we know. For any machine that ignores the input, this is trivially computable (the distance is either $0$ or $\infty$). $\endgroup$
    – tomasz
    Oct 6 '18 at 10:18

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

  • $\begingroup$ Thank you for the further details! I’m a little confused by your third paragraph; the implicit order of quantifiers is throwing me. Do you mean that, for any $k$, there exists an encoding such that $d(x, H)=k$ is undecidable? Or that there exists an encoding such that, for any $k$, $d(x, H)$ is undecidable? $\endgroup$ Oct 6 '18 at 12:58
  • $\begingroup$ @StellaBiderman: For every $k$ there is an encoding. $\endgroup$
    – tomasz
    Oct 6 '18 at 14:48
  • $\begingroup$ @tomasz Cool, that’s what I had figured but the wording seemed to imply the latter to me for some reason. $\endgroup$ Oct 6 '18 at 15:44
  • $\begingroup$ I meant that for every $k$ there exists an encoding. I supplemented my answer with a construction that works for all $k$'s at once. $\endgroup$ Oct 6 '18 at 18:00

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.