News for hackers. Stuff that matters.
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?