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

As people said, a turning machine has infinite memory and program space. Just checking for context and program position doesn’t solve all cases of never halting.

Take for example a program that attempts to calculate the https://en.m.wikipedia.org/wiki/Collatz_conjecture

Some inputs would rapidly get answered. Most won’t. If you can prove it’s halt-able for all inputs, you’ve won a Nobel and will be well off for life.

Good luck.




Consider applying for YC's Spring batch! Applications are open till Feb 11.

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

Search: