Hacker News Reader

Comment by mhmmmmmm | Hacker News Reader

Is reliably detecting if code has any infinite loops feasible? Sounds like the halting problem.

It is exactly the halting problem. Finding some infinite loops is possible, there are even some obvious cases, but finding "any" infinite loops is not. In fact, even the obvious cases are not if you take interrupts into account.

I think that's the joke. In a sci-fi story, that would make the computer explode.

It depends how you define reliably.

The halting problem isn't so relevant in most development, and nothing stops you having a classifier that says "yes", "no" or "maybe". You can identify code that definitely finishes, and you can identify code that definitely doesn't. You can also identify some risky code that probably might. Under condition X, it would go into an infinite loop - even if you're not sure if condition X can be met.

The problem is that you can do this for specific functions/methods, but you cannot do this for a PROGRAM. All programs are "maybe", by definition. You want it to run until you tell it to stop, but you may never tell it to stop. Ergo, all programs have some sort of infinite loop in them somewhere, even if it is buried in your framework or language runtime.

I really don't think that's the definition of a program.

> You want it to run until you tell it to stop,

No? Many programs I don't want to run until I tell them to stop.

Even then, this reduces it to irrelevance.

Yeah, sorry, I wasn’t clear: not the user, the programmer. This is true for almost all programs. Even a simple “print hello world” involves at least one intentional infinite loop: sending bytes to the buffer. The buffer could remain full forever.

Not in the general case, but you could detect specific common patterns.

Reply on news.ycombinator.com