Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

If Idris thinks things may be total that are not, can Idris be used for proofs?

http://docs.idris-lang.org/en/v0.99/tutorial/theorems.html#totality-checking-issues states that:

Secondly, the current implementation has had limited effort put into it so far, so there may still be cases where it believes a function is total which is not. Do not rely on it for your proofs yet!

Does this mean that Idris cannot be relied upon for proofs, or is there a way to create proofs that do not need the totality checker?

like image 574
redfish64 Avatar asked Dec 13 '16 03:12

redfish64


1 Answers

All proof assistants run the risk of implementation bugs (or even hardware bugs!) that may make the system inconsistent and allow users to prove anything. This risk can never be zero. Even if we prove the correctness of the implementation of a proof assistant, that proof also has to be proved in some other formal or informal system, subject to the same risks.

Therefore, what we should expect from a proof assistant is not infallible truth, merely strong evidence of validity. How strong that evidence is depends on our prior information about the trustworthiness of the system, and the extent to which we're able to look at a particular proof and determine whether it makes use of inconsistencies.

So, it's not a clear-cut case how strong evidence Idris proofs constitute. I would say they're quite strong in comparison to informal proofs. Also, Idris proofs don't yet scale as far as Agda or especially Coq proofs, so they are likely feasible to be checked by human inspection for "exploits".

like image 58
András Kovács Avatar answered Nov 12 '22 20:11

András Kovács