4 ms·
And yet there is a correct algorithm — it's either the const yes algorithm or the const no algorithm. We don't _know_ which algorithm it is, but that's not rel
by Twey 3mo ago
And yet there is a correct algorithm — it's either the const yes algorithm or the const no algorithm.
We don't _know_ which algorithm it is, but that's not relevant to the definition of undecidability, which only requires that the algorithm exist.
- masfuerte 3mo agoCheers, I had missed the nuance.
- Twey 3mo agoIn constructive mathematics I think you'd be right: to call a problem decidable would require you to produce the algorithm that decides it, so you couldn't call the Collatz conjecture decidable (nor could you call it undecidable!). But the usual definition of decidability is classical. This is slightly bizarre now I think about it: the definition of decidability allows the algorithm selection to be undecidable!