The following question has been asked few hours ago : How can any statements be proven undecidable? I'd like to ask a similar but more precise question.
Could we imagine that the Syracuse conjecture is undecidable w.r.t. ZF ?
Could we imagine that Riemann conjecture is undecidable ?
Or even simpler, let say we are in 1990, could we imagine that Fermat conjecture is undecidable ?
For all these questions, I would say no. For the latter, here is a (buggy ?) sketch of proof. Take x, y, z, n, positive integers, $n>2$. You can compute easily $x^n+y^n-z^n$. If you get zero, then you get a proof that Fermat's conjecture is false. So if the Fermat's conjecture were undecidable, then I could not get such a proof, so there would not exists a counter-example, so the Fermat's conjecture would be true, and not undecidable.
Is this reasoning flawed ?
This argument would apply to any statement which can by written in the following form : $$ \forall n_i\in \mathbb N, \dotsc, \forall n_k\in \mathbb N, F(x_1,\dotsc,x_k) ,$$ where $F$ is an assertion we can check algorithmically.
I think the Riemann conjecture fits this form. But the Syracuse conjecture, does not (a priori) : you can check that a sequence reach 1, but not that this sequence does not reach 1.