The "generalized collatz conjecture" (rather than 3n+1 and n/2 we use some a*n+k) was proven by the wonderful John Conway to be undecidable [0] by inventing a toy language called FRACTRAN [1] and showing that it was turing complete.
It would be so wonderful to show that 3n+1 and n/2 are enough to compute anything - writing "programs" this way would be fun to look at.
[0]: https://en.wikipedia.org/wiki/Collatz_conjecture#Undecidable...