r/ProgrammingLanguages • u/mttd • 9d ago
Fundamental limits of proofs of programs
https://www.youtube.com/watch?v=MH2uW0apGKU3
u/joonazan 7d ago
I expected a video about difficulties proving complex software but instead it was about the history of the idea and arguments of people doubting the practice.
I disagree with the conclusion being drawn here. Interaction with the real world does not make proofs any less useful. There is a lot of complex software that produces a simple outcome, just efficiently. For such software a formal proof is extremely valuable. And in the formally specified microcontroller case, if I prove that my software works correctly on the formal model, then it's the hardware manufacturer's problem if it doesn't work.
Critics of formal proof typically still advocate for writing software tests. Formal proofs are just better in every way, except cost of maintenance, which is improved by better tools.
1
u/Mclarenf1905 5d ago
Just to add to this even just going through the process of trying to think through how to formally verify your software, even if you can't end up applying it the process itself can be very enlightening / revealing
4
u/InviteQueasy3739 9d ago
I tried to find something about the Curry-Howard correspondence, Church's simple type theory, Coquand’s construction calculus, or Martin-Löf's intuitionistic theory, but I noticed that the focus was different.
I believe that if we were to go in that direction, it would be possible to address paradoxes in type theory (Girard, Hurkens, and Reynolds), the limited principle of omniscience, Markov's principle, Gödel's incompleteness theorem, Statman's theorem, and other related topics.
The explanation is quite interesting, though. I will save it to watch later.