Conway showed that Collatz-like functions are as hard as Halting, by creating a language called FRACTRAN whose programs are Collatz-like functions: https://esolangs.org/wiki/Fractran