Comment by layer8
3 hours ago
An infinite loop doesn’t mean that you can’t prove whatever property you want to prove about your program, if you’ve designed it for that. The limitations coming from undecidability don’t really affect our everyday applications. Unless your application is exactly to determine whether another arbitrary program will halt, that is. But that’s not what the vast majority of software whose bugs we might be concerned about is about.
“We can’t write bug-free software due to the halting problem anyway” is an incorrect argument.
You can't prove a program completed successfully if you can't prove a program even completes at all.
I don't know what properties you think people are trying to pragmatically prove about arbitrary programs but "did the program complete successfully" will always be an important, pragmatic property in software development. Especially in the pragmatic world where so much of our software is chaining smaller programs together to solve a task.
I'm saying we can't write perfectly bug-free software because of the Halting Problem and the inability to prove any given loop will not be infinite until running that loop. Perfect remains the enemy of the good and we certainly write a lot of "bug-free-enough" software without worrying about the Halting Problem day-to-day. But if you are saying the world needs to write perfectly bug free code starting tomorrow because LLMs will find all the vulnerabilities and sandbox escapes the Halting Problem is absolutely one of the reasons we can't ever provably hit that "perfect" target. We still need to find "good enough" or we give up on software development altogether and that's not what I'm advocating. Perfect is the enemy of the good. Mathematically perfect provably does not exist. Software will always have bugs, especially in the world with a threat model of active brute force machines.
You have a serious misunderstanding of the consequences of the undecidability of the Halting Problem. The Halting Problem says you can not prove the precise halting behavior in every problem. Precise and every are very important qualifiers.
If you sacrifice precise and widen it to: "Halt" and "Maybe run forever, but might just take longer than the age of the universe and is thus irrelevant for actual programs we might choose to run" then it is decidable for every problem.
Every means that there exist programs, in the infinity of all programs, that can not be proven. It does not mean that no program can be proven. Programs that are 10^8000000 instructions long that are intentionally obfuscated count in every. Human-designed programs that humans want to be correct and are reasonably sure are correct are extremely well-behaved in comparison and their provable termination can almost always be reasoned about.
Generally speaking, human-designed programs are almost always implicitly being constructed in the space of programs that will terminate (possibly relative to a event loop). At every step of the process you only extend using provably terminating constructions. Few humans will have a loop condition like: "Terminates if the Goldbach Conjecture is true" which is one of those sorts of things that makes it hard to prove termination. Just stay away from unproven conjectures in your loop conditions and you will probably be fine.
I think you have slightly misunderstood the halting problem. There is no computer program H that, for every program P, determines whether P halts. This does not imply that for some particular program Q there is no proof that it halts. In fact in the setting where programs do not take input there is always such a proof (just a trace of the program running to completion). And there are many valid proofs of theorems like "For all x, Q(x) halts" for particular Q. Consider, for example, the case where Q has no control flow at all!