News for hackers. Stuff that matters.
Re:How recursion got into programming: a comedy of errors by andrewflnr on Wednesday July 23, 2014 @09:13PM (#8077794)
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.
Re:How recursion got into programming: a comedy of errors by mtdewcmu on Wednesday July 23, 2014 @11:55PM (#8078152)
I thought languages were Turing-complete, not machines. Languages don't have the problem, because they don't have to have their own memory.
Re:How recursion got into programming: a comedy of errors by Chinjut on Thursday July 24, 2014 @01:29AM (#8078335)
If a language only allows you to specify programs with bounded memory usage, then it will fail to be Turing-complete.