See John H. Conway (1972), Unpredicatable Iterations, In: Proc. 1972 Number Theory Conference, University of Colorado, Boulder, CO. 1972, pp. 49–52. (MR 52 #13717). 

A summary (item 43 in a [paper][1] of Lagarias) says, "This paper states the $3x+1$ problem, and shows that a more general function iteration problem similar in form to the $3x + 1$ problem is computationally undecidable." 

In fact, it shows that in this family of problems, among which $3x+1$ does not appear to stand out in any way, there are undecidable problems. This doesn't prove that $3x+1$ itself is undecidable, but it's definitely food for thought. 


  [1]: https://arxiv.org/pdf/math/0309224.pdf