The Collatz conjecture isn't a decision problem. The natural corresponding decision problem (given an x, does the conjecture hold when starting at all positive integers k less than x) is decidable in constant time.

We don't know what specifically the deciding machine is, but it is either the one that always returns Yes or the one that returns whether or not x is below some finite value. Either case can be solved by only reading a bounded number of bits from the input.

With some work, one can eventually generalize Collatz to make an undecidable problem; this is more or less the basis for FRACTRAN. https://en.wikipedia.org/wiki/FRACTRAN