3 ms·
A constructive proof of existence is exactly a program. (It might not always be a program for a Turing machine, because "constructive" and "computable" are not
by zozbot234 4y ago
A constructive proof of existence is exactly a program. (It might not always be a program for a Turing machine, because "constructive" and "computable" are not exactly the same - but that's beside the point.) Even a non-constructive proof of existence for x can be significant in a programmatic context; it tells you that you can posit an oracle for x (e.g. asking for it to be input by the user, introducing further assumptions based on some special case, etc.) without thereby crashing the program or causing it to behave incorrectly.
- constantcrying 4y ago>but that's beside the point It seems to me that it is an important point though. > Even a non-constructive proof of existence for x can be significant in a programmatic context Which has no relation whatsover to proofs and programms being the same thing.
- zozbot234 4y agoA type-level program is still a program. Non-constructive proofs are addressing the question "will this program crash or go wrong if I extend it to do X, regardless of how I achieve that?", which is exactly the domain of type-level programming.
- logarhythmic 4y agoPrograms and proofs are the same thing though according to the Curry Howard Correspondence, if I'm not wrong.