Why Writing Correct Software Is Hard
72 points by AriFordsham 3 hours ago | 25 comments

turbobutton 58 minutes ago
I believe there's a hard distinction between abstract, mathematical correctness in software and functioning in the real world. Any software that's processing inputs and provides complex workflows to humans has to necessarily deal with the endless vagaries of reality.

That's not to say there isn't value in formal correctness, but the important part is identifying when it's useful and when its more trouble than its worth...

reply
xpct 10 minutes ago
What I've learned this year is that we should be verifying the fridges..
reply
darkwi11ow 34 minutes ago
I agree with you that for most software, verification was historically less of the requirement, however some software always needed to have abstract, mathematical correctness -- think military, medical, industrial automation.

While these areas were main premise of an article when it was written, I think the article really aged well into current time of mass AI/LLM deployment. It shows fundamental limitations of token based systems / symbolic reasoning that LLM espouses internally, while writing correct software. These limitations also apply to humans, however humans mental modelling, being not fully based on symbolic processing, have been historically shown capable of writing correct software systems, while AI/LLM systems have not been proven to be able to do that, and as article shows that with current token based technology it's unlikely they will ever be.

reply
skydhash 15 minutes ago
> however some software always needed to have abstract, mathematical correctness -- think military, medical, industrial automation.

I think those domains has more stringent requirement and a more focused usage, making the classes of inout narrower. A lot of software for B2B and B2C tries to be a kitchen sink and in the result get turned into a ball of mud. Some stuff should just be separate software.

reply
ekidd 37 minutes ago
There is a wide range of software that exists in a "adversarial" environment, including anything facing a network or processing outside data. At a minimum, this software should should not allow an attacker to execute code of their choice on a system handling private data.

This does not require proving systems complete correct, but it does involve proving many properties of these systems.

reply
turbobutton 51 minutes ago
Having been downvoted, I like to clarify that this comes from the experience working in finance with developers with a strong academic background that emphasized on the necessity of formal proof to a point where complexity made actual progress nearly impossible- while simultaneously basing the proof repeatedly on assumptions that did not uphold in practice.
reply
i_am_a_peasant 39 minutes ago
Nah I don't disagree with you. Thing is even if you formally prove that for every input you produce a valid output. In safety certified software, there's the problem that if that input comes from a sensor, a sensor is an inherently probabilistic thing, and it may be that you will have false positives. The best you can do is build a safety case that even if you get false positives you end up in a safe state, but you can't guarantee that they won't ever increase operational costs.
reply
bajard 3 minutes ago
I once had a sensor that rounded the data, so the output unwittingly fitted into a grid. The equations that had to be used on that data gave infinite results because the grid sometimes rounded slopes into vertical lines.

So I had to reconstruct a signal that fitted the data for the equations to work at all. But the reconstruction was no longer measured data. It was made up, and there was no single solution for fitting the data. That meant that, if I wanted, I could "respect the data" but output anything arbitrary.

reply
perching_aix 36 minutes ago
what were some categories of such assumptions, can you name some examples?

a fun one that immediately comes to mind is asserting something holds for reals, but not evaluating whether it holds for IEEE floats, though maybe that's not really a thing in finance due to rounding related rules anyways

reply
kodoman 2 hours ago
I was always interested in formal verification but have only written toy proofs and derived programs.

It's nice to see this older discussion of the topic outside of 'AI does lean' and the assumptions that formally verification is easy or will be easy for AI and you can just switch you brain off.

Build programs that can be verified in the first place is difficult design problem that requires real thought and deep insight of the problem.

reply
bluGill 27 minutes ago
The real question is: for a typical program we prove it - even though we know there are programs we can't prove?

I don't care about the examples given, I care about my word processor, web browser and such. Can we prove them - putting limits on the scripting language

reply
aleph_minus_one 16 minutes ago
> putting limits on the scripting language

Putting limits on a scripting language should not be too hard (even without talking about any correctness proof). And I would bet that for a scripting language where the limits are in a way that "in a correct implementation, it should be highly likely that these limits are actually enforced" (i.e. the specification of the scripting language has no parts that makes you suspicious whether there exists some loophole that a malicious actor could use to overstep the limits), it should actually be possible to write a verified implementation with some effort.

But this is not what people want: for example, basically every evolution of the web standards since HTML5 by the WHATWG was about extending what is possible to do in the scripting language (JavaScript).

reply
BLKNSLVR 10 minutes ago
Only developers see software in it's full resolution. The rest of us see an abstraction; the sheet lying over the top of a device that will never actually be unveiled due to its grotesque appearance. The public can barely even handle the aesthetics of the sheet.

Management and marketing can only cope with a vague, third party description of the sheet.

reply
samiv 2 hours ago
Maybe it's just me but the terminology used in "halting problem" didn't age well.

A lot of modern programs never terminate and thus to me "halting" means no longer able to compute, i.e it's hung/deadlocked.

reply
xnorswap 57 minutes ago
A lot of the language of computer science doesn't translate well to software development.

Computer Science historically being seen as a gateway to software development has done a large disservice to both fields.

reply
pjmlp 4 minutes ago
I think bootcamps did more of a disservice, especially when folks come out of them calling themselves "engineers".
reply
w4der 54 minutes ago
I had a professor once say that a computer scientist has as much to do with computers as an astronomer has to do with telescopes.
reply
Aerolfos 2 minutes ago
Astronomers should have quite a lot to do with telescopes. You might say a modern astronomer has little to do with telescopes as imagined by a layperson, that is some glass lenses in a tube on a tripod, but they're still called "telescopes" even when it's a complex arrangement of mirrors housed inside an observatory (or on a satellite, as is the case of the James-Webb telescope).

And an astronomer should absolutely have understanding of those, their intricacies, the optical equations involved, and how to operate them (usually with automated software, but astronomers are the ones writing that software).

Now an astrophysicist has less to do with telescopes, especially if your field is theoretical cosmology, although they still require familiarity with telescopes, practicalities, how observations are made etc. because that is the basis of their theory. So, a cosmologist vs. an astronomer might be a better analog for a computer scientist vs. a software engineer.

And I know that despite doing my own thesis in cosmology, my studies involved a lot of knowledge and teaching about telescopes, including at least one night of observations (it's pretty boring, things are very automated).

reply
roelschroeven 41 minutes ago
I'm pretty sure its a quote from Dijkstra.
reply
ChrisMarshallNY 41 minutes ago
Reminds me of the classic The Parable of the Toaster:

https://www.glaver.org/ftp/humor/toaster-fable.txt

reply
defrost 38 minutes ago
Tell him he knows little about astronomy and invite him to watch the latest episode of The Sky at Night - a bunch of astronomers gush over a diverse set of telescopes ...

La Palma - Gateway to the Universe (November 9, 2026)

  The team journey to La Palma, where giant new telescopes and cutting-edge science are opening extraordinary new windows on our universe.
~ https://thetvdb.com/series/the-sky-at-night/episodes/1205884...

Roque de los Muchachos Observatory - https://en.wikipedia.org/wiki/Roque_de_los_Muchachos_Observa...

reply
frutiger 43 minutes ago
> as an astronomer has to do with telescopes

A heck of a lot. Your professor clearly does not know much about astronomy.

reply
roelschroeven 37 minutes ago
I think the point is that yes, of course telescopes are important to astronomers, but they're not the essence, they're not what the study is about. They are the tools of the study, not the object of the study.

The same can be said about computers and computer science. I don't think I fully agree with that, but it's interesting to think about.

reply
zombot 43 minutes ago
Don't astronomers use telescopes?
reply
rjbwork 26 minutes ago
And yet, the amount of slop I've seen produced to solve a problem that is trivially reduced to e.g. graph traversal on more than one occasion is astounding. I tend to think it's got more advantages than disadvantages and we should be gatekeeping harder.
reply
wasabiz 54 minutes ago
[dead]
reply