Re:Google's Plop is implemented in Lisp
by sdp on Wednesday November 12, 2008 @11:43PM
(#362701)
The equivalence seems to hold only when the program is complete. Thus, while all proofs can be expressed as programs, not all programs can be expressed as proofs.
[ Parent
| on HN ]
Can't you restrict the domain, and so that the program is complete (for that restricted domain)?
I meant correct, not complete.
I refer to the article on wikipedia which states: "A converse direction is to use a program to extract a proof, given its correctness. This is only feasible if the programming language the program is written for is very richly typed: the development of such type systems has been partly motivated by the wish to make the Curry-Howard correspondence practically relevant."
Programs are equivalent to proofs given their correctness, rather. Additionally, according to the wikipedia article, extracting a proof from a program requires a very richly typed programming language.