重复应用功能

Question

读这个问题让我思考:对于给定的函数f,我们怎么知道这个形式的循环:

while (x > 2)
   x = f(x)

将停止任何价值x？有一些简单的标准吗？

(事实上,f(x) < x对于x > 2似乎并没有帮助,因为该系列可以会聚).

具体来说,我们可以证明这一点为sqrt和log？

Answer 1

对于这些功能,一个证明,ceil(f(x))<x对于x > 2就够了.你可以做一次迭代 - 得到一个整数,然后通过简单的归纳进行.

对于一般情况,最好的想法可能是使用有根据的归纳来证明这一特性.然而,正如Moron在评论中指出的那样,在一般情况下这可能是不可能的,而且在许多情况下,正确的排序很难找​​到.

编辑,回复Amnon的评论:

如果你想使用有根据的归纳法,你必须定义另一个严格的命令,这是有根据的.在你提到的功能的情况下,这并不难:你可以采用x << yif和only if ceil(x) < ceil(y),这<<是新订单的符号.这个顺序当然有根有据的数字大于2,且都sqrt和log相对于它减少-这样你就可以申请有理有据感应.

当然,在一般情况下,这样的订单更难以找到.这在某种程度上也与Hoare逻辑中的完全正确性断言有关,您需要在每个循环结构上保证类似的义务.