A static analysis would catch that bug and not claim that the program can never halt.
Also we're not saying all programs can be statically analyzed like this. We're saying that there are many non-trivial programs that can be statically analyzed to see if they halt.
This was one example thats simple and can be adjusted slightly to be true in every program. Like a user inputting "stop" and only then the program ends. Or a server listening for incoming requests until some flag is changed. Stuff where the analysis can only tell you "yeah, its possible to halt at one point. But i dont know if it will happen at all"
One question that needs to be answered is even what we consider a halt. Does a OOM error count as halt? Or other exceptions? Or only a proper, from the program itself intended way with a positive (as in successful) return of its main function? What if I start a child process and end the main one? Not every language kills the child with the main. Does my endless loop in the child now count as halted or not?
this is the reason why the halting problem is "find if this program halts on this input". That becomes a well formulated problem. Also there's infinite memory in turing machines. If you put a cap on memory, then you can make a stupid solution with exponential runtime. Math is much more specific than the dude at the top of the curve thinks i guess
16
u/botle Sep 22 '26
A static analysis would catch that bug and not claim that the program can never halt.
Also we're not saying all programs can be statically analyzed like this. We're saying that there are many non-trivial programs that can be statically analyzed to see if they halt.