News for hackers. Stuff that matters.
Re:United B772 at Denver on Feb 20th 2021, engine inlet sepa... by Dirlewanger on Saturday February 20, 2021 @06:00PM (#26208845)
One thing that sets software apart from other engineering disciplines is that they are grounded in physics (bits running on a semiconductor doesn't matter for this discussion) and have been around (in some form) for thousands of years. How do we know if a design is sound? We can check it by doing the math. How do we know if a program is sound (what does that even mean? There's our first problem)? Well, we rely on a large compendium of heuristics that are based on nothing but experiences compiled over the past ~60 years. Also, that compendium is constantly being added to. Also, virtually everyone disagrees on what should/shouldn't be in this compendium.
Re:United B772 at Denver on Feb 20th 2021, engine inlet sepa... by just_steve_h on Saturday February 20, 2021 @06:06PM (#26208906)
I'm wading into waters that are way over my head here, but my understanding is that it is possible for software to be provably correct, in the mathematical sense of "proof."

I'm well aware of the admixture of folklore, experience, and caffeine-fueled inspiration that constitutes much of the software that runs our world.

Re:United B772 at Denver on Feb 20th 2021, engine inlet sepa... by archi42 on Sunday February 21, 2021 @08:32AM (#26213313)
Source: I work on static analyzers, so I'm biased to that.

We can not prove everything, as others pointed out the fundamental issue here is the "halting problem". However, this doesn't mean we can't prove anything. Wikipedia says:

> In computability theory, Rice's theorem states that all non-trivial, semantic properties of programs are undecidable.

I often feel like the "trick" is to push the trivial stuff to be as useful as possible. You can work from several vectors: 1. You build better static analyzers (difficult and computationally expensive the further you push it - but that's what we're doing) 2. reduce the complexity of the "analyzed thing" (high level language, assembly,...) to allow for easier analysis, while still being useful (a assembly language only supporting 'nop' is trivial to analyze, but pretty useless overall; otoh you can disallow some constructs in C to make the language easier to analyze).

There are of course other forms of "provably correct". E.g. programming in a language that has proofs attached to it, like coq [which is the name of a proof assistant]. Disclaimer: I've never used coq myself, but know plenty who do. I think that's something that might interest you. [And thanks to the genius who christened that tool: No, seriously, I'm not trying to be rude!]

[edit] Didn't check that link, but maybe you find it interesting https://www.cs.princeton.edu/courses/archive/spring13/cos510... There are of course other approaches than coq, e.g. Isabelle is often mentioned. See the "See also" on https://en.wikipedia.org/wiki/Coq

Re:United B772 at Denver on Feb 20th 2021, engine inlet sepa... by ghaff on Saturday February 20, 2021 @06:25PM (#26209081)
There's work going on in formal verification but it has many limitations.

I'd also point out that in MechE/CivE fields, you're still dependent on materials (and maintenance) working as advertised. It's also often the case that operating conditions just end up being different from what was designed for or certain failure modes weren't considered. See, e.g. the Citibank Building in NYC http://www.slate.com/blogs/the_eye/2014/04/17/the_citicorp_t...

Re:United B772 at Denver on Feb 20th 2021, engine inlet sepa... by bluGill on Saturday February 20, 2021 @09:25PM (#26210279)
You can, but first we need to figure out what correct is in the first place. I can prove hello world doesn't overflow buffers, but it is a bit harder to prove that my font renders the letters vs some random scribbles.
Re:United B772 at Denver on Feb 20th 2021, engine inlet sepa... by rocqua on Sunday February 21, 2021 @05:04AM (#26212256)
It is possible to prove software adheres to a certain specification. This is time consuming, and how feasible it is depends a lot on how your specification was written. It generally also depends on how your software was written.

The big issue is that writing a useful specification can be hard. Especially if you want to also make the specification easy to check.

A side issue is that your proof will make assumptions about how a computer works that are simplified.

Re:United B772 at Denver on Feb 20th 2021, engine inlet sepa... by vvanders on Saturday February 20, 2021 @06:53PM (#26209305)
Have a peek a metastability[1], any time a digital system crosses a clock domain there's basically statistics making sure the whole thing doesn't fall over.

From need a better MTBF? Throw a couple more inline flip-flops.

[1] https://en.m.wikipedia.org/wiki/Metastability_(electronics)

Re:United B772 at Denver on Feb 20th 2021, engine inlet sepa... by Dirlewanger on Saturday February 20, 2021 @07:06PM (#26209405)
I think being able to prove that a program can be correct is getting close to P=NP territory.
Re:United B772 at Denver on Feb 20th 2021, engine inlet sepa... by Raptor22 on Saturday February 20, 2021 @08:50PM (#26210079)
It's very difficult but there have been strides in that direction: http://web1.cs.columbia.edu/~junfeng/09fa-e6998/papers/sel4....
Re:United B772 at Denver on Feb 20th 2021, engine inlet sepa... by aklein on Sunday February 21, 2021 @12:26AM (#26211056)
Cannot prove some program is correct, in general, because that’s effectively the halting problem. But in practice it is sufficient to enforce (prove) the absence of behaviors via constraints like types or contracts.