Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Yes; the Col' function trivially terminates for all n, since Col n' is just

    (if odd n then 3*n+1 else n) `div` 2


That's good then. It shouldn't difficult to bootstrap that to the full Collatz conjecture.


Since the Collatz conjecture is not (known to be) finitely refutable, we cannot encode it as a program whose termination decides the conjecture. If the existence of diverging orbits were disproven though, then we could.


That's a good point & also surprising that such a simple dynamical process can not be proven one way or the other to be an instance of a terminating or non-terminating computation.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: