Hacker News new | past | comments | ask | show | jobs | submit login

Edit:nvm see thread

For collatz, the empty input machine loops over all natural numbers and halts if it finds one which doesn’t eventually reach 1.

To prove that it never halts, you’d have to prove the collatz conjecture. Otherwise you’d have to find the smallest counter example of the collatz conjecture.




Suppose that there exists a natural number that diverges to infinity under the Collatz map. Then the Collatz conjecture would be false, but your machine would still run forever on that diverging number. As far as I am aware, there is no known machine that halts iff the Collatz conjecture is false.


You are correct, thank you




Consider applying for YC's Summer 2025 batch! Applications are open till May 13

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

Search: