Ofra: "is there some reasons to believe that the Collatz conjecture is undecidable?" There is reason to believe a generalized version is undecidable. This was explored by John Conway in "On Unsettleable Arithmetical Problems."1 And this paper proves a version recursively undecidable:
Kurtz, Stuart A., and Janos Simon. "The undecidability of the generalized Collatz problem." International Conference on Theory and Applications of Models of Computation. Springer, Berlin, Heidelberg, 2007. (Springer link.)
Abstract. The Collatz problem, widely known as the $3x + 1$ problem, asks whether or not a certain simple iterative process halts on all inputs. We build on earlier work by J. H. Conway, and show that a natural generalization of the Collatz problem is $\Pi^0_2$ complete.
Here is their generalization:
[![GenCollatz][1]][1]
1Conway, John H. "On unsettleable arithmetical problems." *American Mathematical Monthly* 120.3 (2013): 192-198. ([Jstor link](https://www.jstor.org/stable/10.4169/amer.math.monthly.120.03.192?seq=1#page_scan_tab_contents).) Reprinted in the *Best Writing on Mathematics 2014*.