Leon 无法证明简单递归程序的正确性？

Question

我试过 Leon 的以下程序

object Test10 {

     def sum(n: Int): Int = ({ 
        require(n >= 0)
        if (n == 0) 0
        else    sum(n-1)+1
    })ensuring(res => res==n )    

}

结果--成功

object Test10 {

     def sum(n: Int): Int = ({ 
        require(n >= 0)
        if (n == 0) 0
        else    sum(n-1)+n
    })ensuring(res => res==n*(n+1)/2 )

 }

结果--失败（未终止）

我是不是搞错了，为什么系统不能生产？谁能指导一下？

Answer 1

第二个节目其实不是valid。由于溢出，后置条件对于 n 的大值不正确。当求和溢出时，公式将不再成立。

你可以试试把Int换成BigInt，应该可以吧。由于非线性算法，该问题也很困难。

Leon 没有终止，因为它正在寻找反例（因为程序不是 valid）并且必须展开公式直到溢出。当然直接找到反例报告就更好了，但这是Leon算法的限制。

请注意，您的第一个程序是 valid，因为永远不会溢出。

Leon 无法证明简单递归程序的正确性？

Leon is not able to prove correctness of Simple Recursive program?

leon