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

I'm not sure how to untangle it, but I think you've got your abstraction layers mixed up. Anyway, that infinite tape is critical to Turing completeness. So strictly speaking, a limited-memory computer isn't strictly Turing complete, just close enough as makes no difference, because in practice they can use as much memory as they want, via dynamic memory allocation. When you tell the program it can't use as much memory as it wants, by taking away dynamic allocation, then you're not only not Turing complete, you're not even close to the Turing machine model.


I thought languages were Turing-complete, not machines. Languages don't have the problem, because they don't have to have their own memory.


If a language only allows you to specify programs with bounded memory usage, then it will fail to be Turing-complete.




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

Search: