[WorldMaker]

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.

[voidmain]

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!

[WorldMaker]

I think it's more that I lean into some of the corollaries that directly factor computation time into account. There is no computer program H that for every program P determines whether P halts faster than running P.

You cannot find/prevent every case of an infinite loop at design time/compile time if the only way to determine a complex enough control flow converges towards halting is to run the full program in a live environment.

[Veserv]

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.

[WorldMaker]

But again, the context is not about humans trying very hard to stick to problems in "terminating space" when writing software, but about LLMs with no such compunctions/boundaries finding inputs that break "terminating space assumptions". (Whether or not you also believe that LLMs are capable of staying within the lines of "terminating space" when generating code.)

Generally speaking, yes, humans want to design programs as best they can in the world of safely terminating applications. Humans aren't perfect at it today, given practical real world data such as CVE databases. Trying to hope humans become perfect to safeguard the world against LLMs like the Googler quote way above is the thing I find futile. Humans aren't going to magically get perfect. We need good enough solutions more than we need perfect solutions. The fear is that LLMs can greatly outpace humans in breaking "good enough" than humans can keep up in building "good enough".

[Veserv]

You can prove a program is correct and terminates for all inputs and, absent a hardware or other assumption vulnerability that breaks the abstract machine assumptions, there would be no inputs that "break" anything. In fact, almost any human-designed program that is correct and terminates would not just be provable, but "easy" to prove algorithmically (in the theoretical sense, in a practical sense existing techniques are insufficient to prove complex programs).

Even ignoring isolation guarantees that could generically prevent unbounded escalation for arbitrary programs, you can just reject anything that is not "easy" to prove. Humans are really dumb, so anything that is not directly proven or easy to prove automatically is almost certainly not correct, so you can just err on the safe side and just reject them if you care about global correctness.

[buzzin__]

SolutionNotFound is a perfectly valid return case for my Algo. I start two threads, one searches for a solution, second one terminates the first after one second, if it is still running.

How in the world does the halting problem enters into the picture if my program is bug free or not?

[mrkeen]

The argument is that 'the program returns' is strictly easier to prove than 'the program returns the correct answer'. If the first is impossible, then the second is too.

I'm all in favour of sidestepping the argument by having our languages more resemble System F or some polymorphic lambda calculus.

[WorldMaker]

Though still useful to remember that some of the earliest mathematical write ups of the Halting Problem were also by Alonso Church and directly in the lambda calculus. The Church-Turing Theorem is a lasting reminder that the two worlds imperative and functional describe the same algorithms (form the set of Turing Completeness).

[mrkeen]

It depends on the type system you choose to apply to LC. Simply-typed LC terminates.

You have to include a construct that introduces general recursion to make it Turing complete.

There's a cool practical space within those constraints that needs more exploration.

Non-total functions can call total functions, but not vice-versa.

Imagine a web server whose main loop is non-total, because you want it to stay up. But each route is total, to guarantee termination.