4 ms·

In fact, come to think of it, for any program which 1) uses a bounded amount of memory and 2) has a bounded input (taking "input" as broadly as possible), the h

In fact, come to think of it, for any program which 1) uses a bounded amount of memory and 2) has a bounded input (taking "input" as broadly as possible), the halting problem is always decidable in 2^[bits of state] "steps". There are a lot of programs which satisfy (1) so long as (2) is satisfied, and if (2) is not satisfied then the halting problem is not an interesting problem at all.

just2n 13y ago
The approach would be to fix an upper bound on memory and to enumerate all possible state, running the program each time and determining if all cases terminate or if any runs forever? I think the real crux of the problem is that you can't determine in any of those cases whether the program is going to terminate. Consider bogosort or a brute-force algorithm for solving travelling salesman. These can take millions of years to complete even for small input sizes. Do we consider that an "infinite" runtime?
- belovedeagle 13y ago
  No, the algorithm is to run the program and see if any state is repeated; if it is, the program is in an infinite loop (where "state" means, roughly, all memory and remaining length of input). Of course, this requires 2^[bits of state] bits of memory, and a similar amount of time. Obviously an interesting (read: approximate) solver would use tighter heuristics.
- sp332 13y ago
  Consider bogosort That's true, external inputs and true randomness is not accounted for. (However pseudorandom generators are included!)
willvarfar 13y ago
while(true);
- mietek 13y ago
  So? This can be easily detected by comparing snapshots of memory, including any registers, etc.
- sp332 13y ago
  One bit of state (true/false) means we have to run for 2^1=2 "steps". Since the program does not halt after 2 steps, we have proved that the program will never halt. Easy, huh?
VLM 13y ago
You can also bound time. For a web site / web app, end users aren't going to wait around for 5 days after they click a link... merely spawn your "Halting Problem Tester" and if it doesn't terminate in 10 seconds or whatever your metric is, lie and call it an infinite loop. Yes this is an epic fail from a computer science perspective but its perfectly adequate from an engineering perspective.
- belovedeagle 13y ago
  Or don't lie and explain to what degree of certainty it is an infinite loop...
sp332 13y ago
But even if your program only uses 5 MB of RAM, that's still 2^(5,242,880) or about 1.4x10^1,578,264 steps you have to check.
amalcon 13y ago
This is a special case of the notion that questions about a given computational model can be solved using a more general computational model. See regular expression syntax validation as a context-free grammar, and related notions.

just2n 13y ago

The approach would be to fix an upper bound on memory and to enumerate all possible state, running the program each time and determining if all cases terminate or if any runs forever? I think the real crux of the problem is that you can't determine in any of those cases whether the program is going to terminate. Consider bogosort or a brute-force algorithm for solving travelling salesman. These can take millions of years to complete even for small input sizes. Do we consider that an "infinite" runtime?

belovedeagle 13y ago
No, the algorithm is to run the program and see if any state is repeated; if it is, the program is in an infinite loop (where "state" means, roughly, all memory and remaining length of input). Of course, this requires 2^[bits of state] bits of memory, and a similar amount of time. Obviously an interesting (read: approximate) solver would use tighter heuristics.
sp332 13y ago
Consider bogosort That's true, external inputs and true randomness is not accounted for. (However pseudorandom generators are included!)

willvarfar 13y ago

while(true);

mietek 13y ago
So? This can be easily detected by comparing snapshots of memory, including any registers, etc.
sp332 13y ago
One bit of state (true/false) means we have to run for 2^1=2 "steps". Since the program does not halt after 2 steps, we have proved that the program will never halt. Easy, huh?

VLM 13y ago

You can also bound time. For a web site / web app, end users aren't going to wait around for 5 days after they click a link... merely spawn your "Halting Problem Tester" and if it doesn't terminate in 10 seconds or whatever your metric is, lie and call it an infinite loop. Yes this is an epic fail from a computer science perspective but its perfectly adequate from an engineering perspective.

belovedeagle 13y ago
Or don't lie and explain to what degree of certainty it is an infinite loop...

sp332 13y ago

But even if your program only uses 5 MB of RAM, that's still 2^(5,242,880) or about 1.4x10^1,578,264 steps you have to check.

amalcon 13y ago

This is a special case of the notion that questions about a given computational model can be solved using a more general computational model. See regular expression syntax validation as a context-free grammar, and related notions.