Timeline for Is being close to a Halting set computable?
Current License: CC BY-SA 4.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 7, 2018 at 15:31 | comment | added | tomasz | @none: It might be, but that's conditional on a (particular form of) negation of Collatz. In any case, I think the existing answers are quite satisfactory. | |
| Oct 7, 2018 at 7:40 | comment | added | none | @tomasz Oh yes, you're right. How does this sound: for input $n$, the machine halts if the Collatz (3n+1) iteration eventually reaches 1. The halting set is conjectured to include every $n$, but it might be uncomputable (some generalizations of the Collatz problem are known to be $\Pi^0_2$-complete). Each $n$ gives rise to a $\Pi^0_1$ proposition (the sequence never converges after any number of steps) that might be undecidable. So the distances may also be uncomputable. I feel like it's possible to concoct a definitely uncomputable example along these lines, but don't see one offhand. | |
| Oct 6, 2018 at 21:20 | vote | accept | Stella Biderman | ||
| Oct 6, 2018 at 10:18 | comment | added | tomasz | @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$). | |
| Oct 6, 2018 at 8:41 | answer | added | Andrej Bauer | timeline score: 10 | |
| Oct 6, 2018 at 5:20 | comment | added | none | 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). | |
| Oct 6, 2018 at 4:34 | answer | added | James | timeline score: 13 | |
| Oct 6, 2018 at 4:31 | comment | added | Gerhard Paseman | 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. | |
| Oct 6, 2018 at 4:22 | comment | added | Stella Biderman | @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. | |
| Oct 6, 2018 at 4:10 | comment | added | Gerhard Paseman | 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. | |
| Oct 6, 2018 at 4:00 | history | asked | Stella Biderman | CC BY-SA 4.0 |