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

Technically, the theorem doesn't apply. Actually built computers aren't Turing machines: their memory is finite.

The algorithm to answer if a program running on a deterministic finite-memory machine is trivial: Run until it either halts or repeats a state. Halting means it halts (duh); repeating a state means it doesn't halt. This algorithm is, of course, not implementable.



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

Search: