This is true. The Collatz conjecture of course has a similar heuristic justification for why it should hold: if n is odd then on average 3n+1 is divisible by 2 two times, so on average when given an odd integer we multiply it by 3 and then divide it by 4. This process should eventually get us to the stable orbit starting at 1. Unfortunately I think the Collatz conjecture is one of the most difficult open problems in mathematics today; definitely far more difficult than any of the Millennium Prize problems for instance.
There are also interesting relationships between Collatz-type problems and busy beavers. If a Turing machine with a small number of states wants to run for a large but finite number of steps, the best strategy we know is often for it to implement a Collatz-like algorithm which has the property that it is known to eventually halt. I don’t think anyone understands this very well but it suggests that sufficiently difficult Collatz-like problems may actually be probing too deeply into the properties of arithmetic for PA or even ZFC to be able to decide them. The famous Collatz conjecture itself is probably not this difficult, but it’s impossible to know for certain.
The Collatz conjecture is another famous example of this.
I gave some more examples here: https://www.reddit.com/r/math/comments/9gyh3a/if_you_know_the_factors_of_an_integer_x_can_you/e68u5x4/
This is true. The Collatz conjecture of course has a similar heuristic justification for why it should hold: if n is odd then on average 3n+1 is divisible by 2 two times, so on average when given an odd integer we multiply it by 3 and then divide it by 4. This process should eventually get us to the stable orbit starting at 1. Unfortunately I think the Collatz conjecture is one of the most difficult open problems in mathematics today; definitely far more difficult than any of the Millennium Prize problems for instance.
There are also interesting relationships between Collatz-type problems and busy beavers. If a Turing machine with a small number of states wants to run for a large but finite number of steps, the best strategy we know is often for it to implement a Collatz-like algorithm which has the property that it is known to eventually halt. I don’t think anyone understands this very well but it suggests that sufficiently difficult Collatz-like problems may actually be probing too deeply into the properties of arithmetic for PA or even ZFC to be able to decide them. The famous Collatz conjecture itself is probably not this difficult, but it’s impossible to know for certain.