logoalt Hacker News

pronyesterday at 8:35 PM1 replyview on HN

Oh, if you mean that most algorithm correctness proofs are finitary and therefore don't need to explicitly rely on the excluded middle, that may well be the case, but they certainly don't try to avoid it either. Look at any algorithm paper with a proof of correctness and see how many of them explicitly limit themselves to constructive logic. My point isn't that most algorithm/program proofs need the excluded middle, it's that they don't benefit from not having it, either.


Replies

zozbot234yesterday at 8:39 PM

> My point isn't that most algorithm/program proofs need the excluded middle, it's that they don't benefit from not having it, either.

Because if they benefited from it (in surfacing computational content, which is the whole point of constructive proof) they'd be comprised within the algorithm, not the proof.

show 1 reply