It is plausible that the actual Collatz system is one of these for our standard proof systems.
Why? Consider the following:
The Collatz Conjecture has a lot of structure to it:
It is false for 3n-1
It is undecidable for generalizations of it
It is true empirically, up to 10^20
It is true statistically, a result of Terrence Tao establishes that “almost all initial values of n eventually iterate to less than log(log(log(log(n))))” (or inverse Ackermann)
Additionally, if you look at the undecidable generalizations of the Collatz Conjecture, I expect that you will find them much stronger than the base system. And when people prove such results, they look for the weakest system such that you still have undecidability.
As a result of those considerations, I find it quite implausible that the Collatz Conjecture is undecidable, and I would be interested in what makes you think otherwise.
P vs NP is another candidate for an undecidable problem, dealing as it does with general behaviour of Turing machines that can run programs with rather weak bounds. There’s a lot that we can’t yet prove about about general computation systems, and we have theorems that say we should expect there to be a lot that we can’t ever prove.
More to the point, if you believe P vs. NP is undecidable, then you need to answer the question: why does whatever intuition tells you that, not also tell you that the P versus EXP, NL versus PSPACE, MAEXP versus P/poly, TC0 versus AC0, and NEXP versus ACC questions are similarly undecidable? (In case you don’t know, those are five pairs of complexity classes that have been proved different from each other, sometimes using very sophisticated ideas.)
It would be unsurprising if quite a lot of the problems we can’t solve after trying very hard are actually not solvable.
I am not sure if you mean “unsurprising” in the literal or metaphorical way.
If you mean that it would literally be merely unsurprising, I agree, this is in the realm of possibilities. But I would not call this a “good reason to expect it to be difficult to solve”.
If you mean it as very likely, as to make it a good reason, I disagree. I expect that if we went through Wikipedia’s list of mathematical Conjectures solved since 1995 (which I believe is a good approximation of “Problems that were really hard, and we get to find out how they turned out”), we’d find that most of them were actually resolved, rather than found as undecidable.
Why? Consider the following:
Additionally, if you look at the undecidable generalizations of the Collatz Conjecture, I expect that you will find them much stronger than the base system. And when people prove such results, they look for the weakest system such that you still have undecidability.
As a result of those considerations, I find it quite implausible that the Collatz Conjecture is undecidable, and I would be interested in what makes you think otherwise.
My answer is similar here to Scott Aaronson’s:
I am not sure if you mean “unsurprising” in the literal or metaphorical way.
If you mean that it would literally be merely unsurprising, I agree, this is in the realm of possibilities. But I would not call this a “good reason to expect it to be difficult to solve”.
If you mean it as very likely, as to make it a good reason, I disagree. I expect that if we went through Wikipedia’s list of mathematical Conjectures solved since 1995 (which I believe is a good approximation of “Problems that were really hard, and we get to find out how they turned out”), we’d find that most of them were actually resolved, rather than found as undecidable.