《从问题到程序：用Python学编程和计算》——3.3　程序终止性

本节书摘来自华章计算机《从问题到程序：用Python学编程和计算》一书中的第3章，第3.3节,作者：裘宗燕 更多章节内容可以访问云栖社区“华章计算机”公众号查看。

3.3　程序终止性

本节讨论一个与循环和递归有关的重要问题：程序的终止性。一个程序的执行是否一定结束，这是一个很重要的问题。例如程序对所有可能的输入是否都能结束（终止），或者函数对所有的参数是否都能终止并给出结果。如果一个程序对于某些输入（或一个函数对于某些参数）不终止，遇到这些输入或参数，程序就会无穷无尽地运行下去，既不给出结果，也不报告运行错误。这种情况通常也不符合用户的需要。在很多实际应用中，这种情况是绝对不能允许的。请考虑一部汽车的刹车控制程序。
首先可以想到，只要程序里的每个基本语句都终止，直线型和分支型程序就必然终止。但循环程序的情况则不同，即使循环体中的语句保证终止，这个循环也可能不终止。如果在一个while循环的执行中，循环体里语句的执行不能把循环条件变为假，这个循环就会无休止地继续下去，循环之后的语句永远也得不到执行的机会。递归函数（递归程序）也存在类似的问题，它也可能无穷无尽地递归调用下去 。
但另一方面，有些程序可能确实需要运行很长时间，等了很久也没有得到结果，并不一定说明这个程序不能结束。
3.3.1　调和级数的部分和
看一个例子：由数学知识可知，下面调和级数的部分和增长非常慢：

def harmony(num):
    s = 0
    n = 0
    while s < num:
        n += 1
        s += 1/n
    return n

用一些参数值做试验：

print(harmony(5))
print(harmony(10))
print(harmony(15))
print(harmony(20))

可以看到，程序输出3个结果后很长时间都没有进一步的动静。在这种情况下，我们没有办法判定究竟是程序出了问题，永远不会结束，还是过一会就能得到结果。为了了解程序运行的情况，可以考虑在循环里加一个输出信息的语句：

if n % 1000000 == 0:
            print(s)

这个语句要求每一百万次循环输出一次部分和。在执行harmony(20)时，可以看到输出的值慢慢地增长。只要等的时间足够长就能得到结果。但如果调用harmony(25)，考虑到浮点数的计算误差等，我们还能得到结果吗？请读者考虑这个问题。
3.3.2　程序终止性不可判定
有关程序的终止性问题，被人们称为计算机之父的英国数学家图灵给出了一个理论结论（1934年）：程序终止性问题是不可判定的。也就是说，我们不可能做出一个判断程序终止性的软件工具，使其对任何程序和程序的任何输入，都能给出该程序将终止或不终止的结论。在实际中，有时判断一个程序是否终止也很困难。看下面的简单程序。
【例】本问题称为Collatz猜想（Collatz conjecture）。德国数学家Lothar Collatz猜想下面函数对所有正整数n终止：

def collatz(n):
    while n != 1:
        if n%2 == 0:        # n is even
            n = n//2
        else:                # n is odd
            n = n * 3 + 1
    return 1

人们用大量的正整数试验这个函数，发现它都终止，但至今无人能严格证明Collatz猜想是正确的（即函数collatz终止），也没人能证明这个猜想不正确，没找到能使collatz函数不终止的输入。人们通过试验发现，采用一些参数，变量n可能经历非常大的值或反复上下跳跃，但最终都能达到1，但却没有找到任何有价值的规律。
读者可以基于上面程序做一些试验，例如检查它对具体的参数迭代多少次后才能达到1，或者考察在此过程中曾经达到的最大数值等。
虽然有上面的理论结论，我们不可能做出完成终止性判断的系统（工具），但在实际工作中还是需要考虑这个问题，通过对具体程序的具体分析，设法确定自己写出的程序一定能终止。这里的基本问题就是检查程序里的循环或者递归，设法确认它们一定终止。只要迭代器给出的序列有穷，相应的for循环一定终止。对于while循环，一种常用方法是设计一个基于循环中变量的整型表达式，证明该表达式的值随着一次次迭代严格下降，但其值一定不小于某个数（例如0）。如果这样的表达式存在，该循环就一定终止。这里不再深入，有关算法的专门书籍都有这方面讨论。
重看前面的程序，其中的大多数循环的终止性都比较容易判断。另一些程序的终止性有数学上的保证，例如牛顿迭代法等。