←back to thread

108 points BerislavLopac | 1 comments | | HN request time: 0.204s | source
Show context
graycat ◴[] 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 #
1. userbinator ◴[] No.43714513[source]
More information on the algorithm to do so: https://en.wikipedia.org/wiki/Cycle_detection