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 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.

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 The $3x + 1$ problem: An annotated bibliography 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.