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

A finite memory machine is a finite state machine. These are not Turing complete. The notion of Turing completeness becomes uninteresting if we can't even draw this distinction.

"dynamic memory allocation" may not have been the right term to use to denote moving beyond finite state machines, for an audience which wants to consider a Turing machine as having statically allocated infinite memory. But it makes sense if you think of a Turing machine's memory as only storing enough data for the portion of the tape which has already been accessed, and allocating new memory as new tape regions are needed.

It's true that the actual machine sitting on your desk only has a fixed finite memory. In that sense, without a peripheral unbounded store, it's not properly Turing complete.

It's also true that we often find it convenient to analyze it as Turing complete anyway, but this abstraction basically goes hand-in-hand with abstracting away its memory limitations. I don't see any point in pretending you can be Turing complete using only programs with a statically given memory bound (which amounts to a logarithmic bound on the number of states in a corresponding finite state machine); if we're going to pretend, let's pretend the memory is effectively infinite as well.



The problem with analyzing programs in the context of a fixed memory limit is that you would have to revisit all of the proofs whenever the fixed limit was increased. If you can prove something true for unlimited memory, it's also true for any limited amount of memory.

>>we often find it convenient to analyze it as Turing complete anyway

It's convenient, because the proofs will still be true even if memory sizes grow by 500x. Turing machines clearly don't have a real, material existence, similarly to real numbers (assuming that all actual numbers are finite). Real numbers can be considered as modeling integers that are arbitrarily large.




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

Search: