News for hackers. Stuff that matters.
Re:Formal methods: Just good engineering practice? by creshal on Monday June 24, 2024 @02:14AM (#40773004)
> In theory, your software itself provides the proof that it does what it claims.

If you manage to solve the halting problem first.

Re:Formal methods: Just good engineering practice? by seethedeaduu on Monday June 24, 2024 @02:20AM (#40773023)
People keep summoning the halting problem in unrelated contexts to handwave things awayvas impossible.
Re:Formal methods: Just good engineering practice? by coldtea on Monday June 24, 2024 @03:58AM (#40773507)
Except in this case, where it's 100% fitting.
Re:Formal methods: Just good engineering practice? by auggierose on Monday June 24, 2024 @04:04AM (#40773530)
It is only fitting if you think of providing the proof as a push button technology. That makes as much sense as thinking of providing the software itself as a push button technology.
Re:Formal methods: Just good engineering practice? by coldtea on Monday June 24, 2024 @04:44AM (#40773747)
It has nothing to do with the proof as a push button technology.

Adding annotations to the code for example is not a workaround for the halting problem.

(Working with a subset that's not-turing complete is, but that doesn't cover the general case the parent calls for, and is not practical with current software development languages and practices).

Re:Formal methods: Just good engineering practice? by auggierose on Monday June 24, 2024 @05:13AM (#40773895)
Not sure if we are talking about the same thing. If you know why your software is correct, you can write that down as a proof (if you have a language which allows you to do that). If you don't know why your software is correct, well, maybe you should not ship it, because maybe it isn't correct.

So yes, it is all about push button technology here. If you are willing to put in the work to write down the proof yourself, instead of expecting a magical entity to generate it for you, then it is possible. All the halting problem says is that there is no such magical entity. You will need to know why your software is correct.

Re:Formal methods: Just good engineering practice? by adrianN on Monday June 24, 2024 @10:32AM (#40776532)
The halting problem is a worst case statement. For almost all functions a programmer encounters in their job it is trivial to solve.
Re:Formal methods: Just good engineering practice? by Thiez on Monday June 24, 2024 @02:45PM (#40779358)
Exactly. In practice you always want each loop iteration to perform some action that brings you closer to some desired end state. That loop invariant + some notion of getting closer to the end is usually the proof you need to prove termination. A loop where you don't have these things is almost certainly a bug.

The vast majority of loops iterate over some finite collection of elements and are thus guaranteed to terminate. Tricky cases are stuff like "I will repeat this operation until the output stops changing".

Re:Formal methods: Just good engineering practice? by coldtea on Monday June 24, 2024 @05:35PM (#40781094)
>Exactly. In practice you always want each loop iteration to perform some action that brings you closer to some desired end state. That loop invariant + some notion of getting closer to the end is usually the proof you need to prove termination.

If you're making Space Shuttle software from scratch yes. In practice for 99% of current mainstream development you depend on piles upon piles of dependencies, which might or might not check those loop invariants correctly, or might have a (trivial to add) endless blocking timeout, a deadlock, and many other wonderful things.

Usually they're not even set in stone, you'll update to the next version, and if they introduced such an issue, there's lots of fun to be had.

Nobody doubted you can have formal proofs for algorithms, or checked software in certain conditions and for certain controlled environments (e.g. using MISRA C and such) (in fact, I support this in a comment elsewhere in this thread).

The objection is to the idea that this is applicable (or trivially applicable, and we just aren't doing it out of laziness or something) to regular software development.

Re:Formal methods: Just good engineering practice? by ulbu on Monday June 24, 2024 @04:32AM (#40773670)
how?
Re:Formal methods: Just good engineering practice? by auggierose on Monday June 24, 2024 @04:03AM (#40773527)
No, you just need to require that somebody who writes the software, also knows why the software halts, and documents the reason properly.
Re:Formal methods: Just good engineering practice? by adrianN on Monday June 24, 2024 @02:48AM (#40773130)
The calculations you do to make sure that the bridge doesn’t collapse also require that the steel matched whatever properties your formula assumes. That doesn’t make the calculations useless.
Re:Formal methods: Just good engineering practice? by ffsm8 on Monday June 24, 2024 @02:47AM (#40773123)
That doesn't need to be solved.

Continuing the stream of inputs holds no meaning once you've tested every possible permutation (branch coverage) beyond checking for memory leaks. Every software has a finite amount of states it can hold, most developers just erroneously expect some states to be unlikely or impossible to reach.

Re:Formal methods: Just good engineering practice? by pyrale on Monday June 24, 2024 @02:58AM (#40773179)
The halting problem is not an actual issue. It’s a darling of computer science classes, but is you need to prove that your program halts, it’s not that hard to write it in a language subset that is not turing-complete.
Re:Formal methods: Just good engineering practice? by riku_iki on Monday June 24, 2024 @03:02PM (#40779501)
> If you manage to solve the halting problem first.

there is a large slice of algorithms, which are possible to prove that they are not affected by halting problem. I think having tooling for this slice of algorithms is already a big win.