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

Minor detail, but the undecidability Halting Problem strictly requires an infinite tape (infinite storage space).

In "practice", if you could call it such, a computer with limited memory becomes a "linear bounded automaton" and the Halting Problem is decidable; cf. http://cs.stackexchange.com/q/22925

Of course, big enough memory can mean that it can be impossible to detect termination before the heat death of the universe - we are talking theory here.



Consider applying for YC's Summer 2026 batch! Applications are open till May 4

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

Search: