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

> Sure, but in practice, most people loosen that requirement. Otherwise, no implemented language is Turing-complete.

The common hand-wave for this is to assume that (1) the machine has big enough storage for the problem, otherwise you could not have the problem in the first place and (2) the algorithm can have an arbitrary time/space trade-off, so if it needed more memory than the physical bound, you could just have it run longer. Note that (1) is a non-sequitur, since the input tape is usually not included in the machine memory in the first place.



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

Search: