7 ms·
The Curry-Howard isomorphism[1] is usually described as a correspondence between computer programs and mathematical proofs. What they usually mean, but don't us
by mcguire 10y ago
The Curry-Howard isomorphism[1] is usually described as a correspondence between computer programs and mathematical proofs. What they usually mean, but don't usually say, is that the actual correspondence is between computer programs and proofs in intuitionistic or constructive logic[2]. (Natural deduction is a lovely example[3].) The important difference between constructive and "classical" logic is that in the former you cannot use the law of the excluded middle or double-negation-elimination.
One way this difference shows itself is in proofs of existence: rather than just demonstrating that something exists (by virtue of it not-not-existing), you have to create an example of it. This is similar to a program, where you cannot demonstrate that 2+2 has some value and then print "4"; instead you have to calculate 4 before you can print it.
Another weird place it shows up[4] is in Prolog, which uses classical first order logic by the closed-world assumption[5]: anything you cannot prove is false.
[1] https://en.wikipedia.org/wiki/Curry%E2%80%93Howard_correspondence https://en.wikipedia.org/wiki/Curry%E2%80%93Howard_correspon...
[2] https://en.wikipedia.org/wiki/Intuitionistic_logic https://en.wikipedia.org/wiki/Intuitionistic_logic
[3] https://en.wikipedia.org/wiki/Natural_deduction https://en.wikipedia.org/wiki/Natural_deduction
[4] At least I thought so, one morning in the shower.
[5] https://en.wikipedia.org/wiki/Closed-world_assumption https://en.wikipedia.org/wiki/Closed-world_assumption