Proofs and programs

Here’s an interesting quote omparing writing proofs and writing programs:

Building proofs and programs are very similar activities, but there is one important difference: when looking for a proof it is often enough to find one, however complex it is. On the other hand, not all programs satisfying a specification are alike: even if the eventual result is the same, efficient programs must be preferred. The idea that the details of proofs do not matter—usually called proof irrelevance—clearly justifies letting the computer search for proofs …

The quote is saying “Any proof will do, but among programs that do the same job, more efficient programs are better.” And this is certainly true, depending on what you want from a proof.

Proofs serve two main purposes: to establish that a proposition is true, and to show why it is true. If you’re only interested in the existence of a proof, then yes, any proof will do. But proofs have a sort of pedagogical efficiency just as programs have an execution efficiency. Given two proofs of the same proposition, the more enlightening proof is better by that criteria.

I assume the authors of the above quote would not disagree because they say it is often enough to find one, implying that for some purposes simpler proofs are better. And existence does come first: a complex proof that exists is better than an elegant proof that does not exist! Once you have a proof you may want to look for a simpler proof. Or not, depending on your purposes. Maybe you have an elegant proof that you’re convinced must be essentially true, even if you doubt some details. In that case, you might want to complement it with a machine-verifiable proof, no matter how complex.

Source: Interactive Theorem Proving and Program Development
Coq’Art: The Calculus of Inductive Constructions

3 thoughts on “Proofs and programs

  1. I agree completely.

    My experience is that once you’ve got a formal proof you tend to generalise it, refactor it, specialise it, and generally explore the space of related proofs and theorems much as you do with programs.

    I therefore don’t think it’s true that it’s normally enough to find a proof and stop.

  2. I’m put in mind of Paul Erdős’s notion of The Book, in which God keeps the most elegant proof of each mathematical theorem. “You don’t have to believe in God,” (which Erdős himself didn’t, of course), “but you should believe in The Book.”

Leave a Reply

Your email address will not be published. Required fields are marked *