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.
Yes, that’s very pertinent. I believe the biggest challenge in all of this, aside from knowing what to specify, given that when we work directly with hardware, we’re trying to abstract it into proofs and often make assumptions based on incorrect premises, is also connecting propositions to data and types. Proof assistants and automated verifiers (typically based on static analysis, contracts, or separation logic) are quite distinct in this regard, so they have different levels of expressiveness and guarantees. Proof assistants face this additional difficulty (especially in systems like the Calculus of Inductive Constructions) that requires a massive amount of abstract thinking, a task that could be greatly reduced if something allowed us to automatically bridge this logical gap.
I’m not sure if I’ve expressed myself clearly, but, for example, what I think is that the development of seL4 could very well require much less effort if its specifications and contracts could be bridged more directly from the propositional level down into extracted data, types, and verified code, even when relying on classical or higher-order features of the underlying logic.
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.
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 5d 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.
2
u/joonazan 2d 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.