5 ms·
But the halting problem is specifically for any kind of program. Otherwise you can just say that every codebase is smaller than X petabytes anyway so it’s alway
by brap 1y ago
But the halting problem is specifically for any kind of program. Otherwise you can just say that every codebase is smaller than X petabytes anyway so it’s always decidable.
- JohnKemeny 1y agoNo, 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 1y 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 1y agoWell, the post I responded to was a respons to a post about point 2. I simply reiterated OP's point.
- chriswarbo 1y 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 1y ago[deleted]
- deleted 1y ago[deleted]