4 ms·
I guess the short way to say it is that "undecidable" doesn't mean "it can't ever be decided", just not always. And of course all programs of practical signifi
by mmoskal 2y ago
I guess the short way to say it is that "undecidable" doesn't mean "it can't ever be decided", just not always.
And of course all programs of practical significance are finite state machines (since there is only a finite number of atoms in the universe).
- XorNot 2y agoIsn't the point closer to, humans simply go "hey that seems to be taking a little long?" when a program doesn't halt, so why couldn't a machine? Basically a fairly obvious constraint on the solution space is "completes in less then N wall-clock time".
- roywiggins 2y agoYou can definitely detect a portion of halting machines this way, but it's probably a relatively small portion because the Busy Beaver numbers grow inconceivably quickly: the longest-running machines that halt can go practically forever, you'd need more time than the universe has negentropy left to detect them.