Here we should mention the Wang tile interpretation of the 3n+1 process, due to @cosmo and Matthew Cook, that I will try to summarize (@cosmo are you here?). According to it, we may view this process as a sort of cellular automaton on a 2D regular grid that evolves either downward from a horizontal alignment of cells, or leftward from a vertical alignment. Each cell can be in any of 6 different states, provided that the contiguous egdes of all pairs of neighboring tiles have the same color (out of 3 colors).
What is really interesting is that this automaton has been shown to convert the base 3 (vertical) representation of any arbitrary number into its base 2 representation (horizontally). The required number of steps for this conversion to be completed is exactly the size of the number in base 2 (as far as I understand…). In the same time, this automaton also computes the base 6 and base 3/2 representations along the diagonal directions. Thus, it seems unlikely that we can compute other things like a prime factorization, unless it can be diverted from its primary function and do something else in the long run… Plus the fact that is expected to “halt” within a number of iterations at most 30 times the initial number of digits in base 2.
See this post for more details.