←back to thread

The Halting Problem is a terrible example of NP-Harder

(buttondown.com)
108 points BerislavLopac | 1 comments | 17 Apr 25 07:34 UTC | HN request time: 0.365s | source
Show context
graycat ◴[17 Apr 25 08:08 UTC] No.43714234[source]▶
Well, for a computer that is a finite state machine there are only finitely many states. So, in finite time the machine will either (a) halt or (b) return to an earlier state and, thus, be in an infinite loop. So, in this case can tell if the "program will stop" and, thus, solve "the halting problem".

Uh, we also assume that before we start, we can look at the design of "the machine" and know how many states there can be and from the speed of the machine how many new states are visited each second. So, we will know how long we have to wait before we see either (a) or (b).

replies(6): >>43714273 #>>43714285 #>>43714402 #>>43714513 #>>43714742 #>>43717019 #
brap ◴[17 Apr 25 08:18 UTC] No.43714273[source]▶
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.
replies(1): >>43714470 #
JohnKemeny ◴[17 Apr 25 09:00 UTC] No.43714470[source]▶
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.

replies(4): >>43714842 #>>43714943 #>>43714992 #>>43717711 #
1. chriswarbo ◴[17 Apr 25 10:26 UTC] No.43714943[source]▶
Architectures 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 ....)