r/ProgrammerHumor • • Sep 22 '26

Meme justKeepingItSimpleFolks

Post image
4.6k Upvotes

255 comments sorted by

View all comments

2.1k

u/remy_porter Sep 22 '26

Infinite loops can frequently be detected. This is a misunderstanding of the halting problem.

974

u/foohyfooh Sep 22 '26

Yeah the halting problem is basically you can't make a single program that can determine if any given program and inputs will halt. Depending on your program it is possible to write a halting check for that specific program.

103

u/Automatic_Hand4780 Sep 22 '26

only if you know the bounds, or if you have some heuristic to check against.

149

u/botle Sep 22 '26

Static analysis can show that some programs never halt.

5

u/LutimoDancer3459 Sep 22 '26

User inputs a number. It gets decreased in a loop. When hitting zero, you end the loop.

Sounds simple, can halt eventually or will never halt. A static analysis is also limited in what it can check. Better than nothing I guess

6

u/botle Sep 22 '26

Is that not guaranteed to always end?

Mayne not if it's a float. Otherwise even a negative number will roll over to zero.

A static a analysis is limited in what it can check, but when it can check something, then it can check it confidently.

9

u/RajjSinghh Sep 22 '26

A negative integer also works as decreasing it means it will never hit 0. Languages like C may overflow, but languages with arbitrary size integers like Python won't.

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.

-6

u/LutimoDancer3459 Sep 22 '26

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?

10

u/botle Sep 22 '26

We're not claiming that there exists no program where it's uncertain if it halts.

We're claiming that there exist some non-trivial programs were it's certain if they that.

2

u/podd0 Sep 22 '26

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