3 ms·
No, the halting problem doesn't hold when you have finite memory (as per OP's point). As OP says, after finitely many iterations (at most 2^n many), you have t
by JohnKemeny 2y ago
No, the halting problem doesn't hold when you have finite memory (as per OP's point).
As OP says, after finitely many iterations (at most 2^n many), you have to be back at a previously seen state, and can terminate.
- tromp 2y agoThe halting problem requires both 1) unlimited length of programs whose halting behaviour is to be decided (so it can not be limited to program of at most 10 petabytes) 2) for those programs to have unlimited memory available You're arguing about point 2) in response to a post about point 1).
- JohnKemeny 2y agoWell, the post I responded to was a respons to a post about point 2. I simply reiterated OP's point.
- chriswarbo 2y agoArchitectures like x86 can only address a finite amount of RAM, since they have a fixed word size (e.g. 64 bits). However, their memory is still unlimited, since they can read and write to arbitrary IO devices (HDDs, SSDs, S3, etc.); though those operations aren't constant time, they're O(sqrt(n)), since they require more and more layers of indirection (e.g. using an SSD to store the S3 URL of the address of ....)
- deleted 2y ago[deleted]
- deleted 2y ago[deleted]