↖  电脑前传(2)：计算-3..

可计算数不可计算

简单总结一下：每台专用机能够产生一个可计算序列，对应一个可计算数，专用机的计算过程可以编码成一个描述数，通用机执行这个描述就可以产生专用机同样的可计算序列。

我们是否就此可以得出结论：通用机是否可以算出所有的可计算数？

似乎可以回答“是”。前提是能够设计出所有专用机，用今天的话说就是编写出所有可能的软件，并在计算机上执行这些软件。

软件数可数但无穷多，因此完成这个任务的前提是编制无穷多个软件，再无穷无尽地执行下去，这实际上是做不到的。

正确答案应该是“否”。尽管每个可计算数都可以算出来，而且所有可计算数是可数的，但是不存在枚举出所有可计算数的算法，只能一个一个地算，不存在找到所有可计算数的通用算法，这就是“可计算数不可计算”的含义。

证明方法是反用康托的对角线法，这就是图灵在论文第8节提到的“对角线法的应用”。既然可计算数是可数的，那就可以把所有可计算数排成队列，用对角线法构造出一个新数。

根据对角线法，这个新数与队列中的任何可计算数都不同，因此是不可计算数。然而，构造这个新数的过程是一个典型的可计算过程，因此这个新数是可计算数。这就导致了矛盾。

矛盾的根源在于不可能对可计算数实行对角线法，上述可计算数队列根本没办法构造出来。

自然数可以逐个枚举，因此找出所有可计算数最直接的思路是逐个检查所有自然数，看它是否描述了一台能够产生一个可计算数的专用图灵机。

假定机器D能够检查一个整数是否符合要求的描述数，通用机U能够按符合要求的描述数执行并产生对应的可计算数，机器H按照对角线法调度U和D来逐位产生新数。

下面这个系统开始运行。

H从i=1开始逐个检查所有自然数，用r(i)来记录已找到的可计算数的个数，r(1)=0，之后的规则是：如果整数i不是符合要求的描述数，则r(i)=r(i-1)；反之，r(i) = r(i-1)+1，同时H调用U计算出i对应的可计算数的前r(i)位，并把第r(i)位添加到新数的第r(i)位。

三台机器似乎可以联合起来按部就班地运行了。

但机器H终究会碰到自己所对应的那个整数，设为k。因为H的一切行为正常，因此k是一个符合要求的描述数，D也应该做出这样的判断，按规则H就会把k转换成标准描述，交给U去执行计算任务，也就是产生k对应的可计算数的r(k)位。

执行描述数k的机器U就等于H，它会依次产生r(1), r(2),…, r(k-1)，但要产生r(k)时却回到了任务本身，陷入无休止的死循环，永远产生不出r(k)。

出现上述困境，说明假设错误，因此，不存在能够生成所有可计算数的通用算法，也不存在能够判别任何指定数是否是可计算数的万能机器。这意味着：软件要一个一个地去编，软件中的漏洞也要一个一个地去查，没有万能机器能帮我们完成这个任务。

判定问题

从论文第9节“可计算数的范畴”开始剩下的十多页，是可计算数在判定问题中的应用，被《图灵传记》[7]的作者安德鲁·霍奇斯(Andrew Hodges)誉为“有史以来数学类论文中最不寻常的部分”。其实上一节已经体现了证明的精髓。

“判定问题(Entcheidunsproblem)”这个德文词是希尔伯特的助手海因里希·贝曼(Heinrich Behmann, 1891—1970)创造的。在贝曼的想象中，判定过程是这样的：

这个问题的一个特性至关重要，就是证明过程只允许根据指令进行纯机械式的计算，不允许掺杂任何严格意义上的思考活动。如果愿意，我们可以说机械的或像机器一样地思考（说不定以后我们可以用机器来运行这种过程）。

贝曼这番话是1921年5月10日在哥廷根数学协会关于判定问题的座谈会中讲到的（这个材料近年才公开[8]）。

1928年，已届暮年的希尔伯特在国际数学家大会上将判定问题列为三大问题之一，他梦想得到一个肯定回答。

英国数学家哈代对此嗤之以鼻，他指出[7]：“当然不存在这样的公理，我们应该感到庆幸，因为如果我们找到了一套机械的规则，为所有数学问题提供解决方案，那么数学家的活动就将结束。”

哈代和希尔伯特各执一词时，图灵还在备考剑桥大学，攻读的正是哈代的《纯数学教程》。四年大学毕业后，他才第一次听到判定问题，躺在剑桥草坪初夏温暖的阳光下，破解了两大顶级数学家争执的世纪难题。

那是1936年，图灵24岁，一个刚刚大学毕业的翩翩少年，为机械意义上的计算画出了明确边界。

这正是： 数可数，非常数

        实数不可数，实在在何处？

        计算又可数，其他为何物？

        其他可想不可及

        机可及，图灵机 ■

脚注：

1 岳麓书院讲堂中一副对联的前三句，由旷敏本撰书。旷敏本（1699—1782年），乾隆十九年（1754年）被聘为岳麓书院山长，即现代意义上的“院长”。

2 丢番图方程(Diophantine equation)：有一个或者几个变量的整系数方程，它们的求解仅仅在整数范围内进行。丢番图是古代希腊人，被誉为代数学的鼻祖，他早在公元3世纪就开始研究不定方程，因此常称不定方程为丢番图方程。

参考文献：

[1] Cantor G. Ueber eine elementare Frage der Mannigfaltigkeitslehre[M]// Jahresbericht der Deutsche Mathematiker-Vereinigung 1890-1891. 1891,1:75-78.

[2] Petzold C. The Annotated Turing: A Guided Tour Through Alan Turing’s Historic Paper on Computability and the Turing Machine[M]. John Wiley & Sons, 2011. （中文版： 杨卫东,朱皓 等译. 图灵的秘密. 人民邮电出版社, 2012）

[3] Church A. A Note on the Entcheidunsproblem[J]. Journal of Symbolic Logic. 1936,1(1):40-41.

[4] Church A. An unsolvable problem of elementary number theory[J]. American Journal of Mathematics. 1936,58 (2): 345-363.

[5] Turing A. On Computable Numbers, with an Application to the Entscheidungsproblem[C]// Proceedings of the London Mathematical Society. 1936:230-65.

[6] Turing A. Systems of Logic Based on Ordinals (PhD thesis). Princeton University. doi:10.1112/plms/s2-45.1.161.

[7] Hodges A. Alan Turing: The Enigma[M]. Simon & Schuster, 1983: 104.

[8] Ewald W. From Kant to Hilbert: A Source Book in the Foundation of Mathematics[M]. Oxford University Press. 1996, Vol. II, 1113.

本页Url