[敬请读者注意] 本人保留本文的全部著作权利。如果哪位读者使用本文所描述内容，请务必如实引用并明白注明本文出处。如果本人发现任何人擅自使用本文任何部分内容而不明白注明出处，恕本人在网上广泛公布侵权者姓名。敬请各位读者注意，谢谢！

计算机与计算模式 (2)   何谓计算？

程京德

接下来我们必须讨论清楚的是一个抽象概念：“计算”。本文将仅仅讨论作为抽象概念的“计算”，而暂且不讨论在计算机上执行的实际计算过程。因此，我们在这里讨论的“计算”和目前世界上到处都是的“XX计算”不是在一个概念层面上的。所谓的各种“XX计算”，是我们将在后文讨论的对象。

对于“计算”这一抽象概念的科学认识始于20世纪30年代逻辑学家（哲学家）们对在研究和建立经典数理逻辑时所提出的所谓“基本问题(Entscheidungsproblem)”[1]的探讨。20世纪20年代，德国逻辑学家、数学家希尔伯特(D. Hilbert, 1862-1943)提出了其著名的“希尔伯特计划(Hilbert's program)”，试图通过一系列基础（形式化）工作来奠定数学的基础，使得数学在形式化基础上是一致的、无矛盾的；更准确地说，希尔伯特希望以基于有穷观点（finitistic means,亦即，不假定和利用实无穷）的形式化公理方法，不但要从数学中排除那些已知的悖论，而且要保证建立在形式化基础之上的数学根本不可能出现悖论。“希尔伯特计划”中的工作之一就是“基本问题”：“能否找到一种基于有穷观点的能行方法(effective method, effectively calculable)，它能够被用来判定任何一个给定的形式命题的真假？”，其经典数理逻辑方式的表述第一次出现在希尔伯特和阿克曼的名著“数理逻辑基础”[1]中。正是对这“基本问题”中要求的所谓“基于有穷观点的能行方法”的认识和形式化工作，导致了对抽象概念“计算”的认识和建立。由此历史背景可知，所谓“计算”，与许多抽象数学概念一样，本质上是一个逻辑学家和数学家为了研究和建立经典数理逻辑从领域内的需要出发而定义的一个抽象概念，其初始动机与“计算机”毫不相干，也与现实世界无关。

在20世纪30年代，为了解决“基本问题”和形式化“基于有穷观点的能行方法”，几位逻辑学家几乎同时（1936年）各自独立地提出了几个关于“可计算”的数学模型来形式地表达“基于有穷观点的能行方法”。其中有：奥地利逻辑学家、数学家哥德尔(K.F. Godel,1906-1978)和美国逻辑学家、数学家克莱尼(S.C. Kleene,1909-1994)的递归函数模型[2,3], 美国逻辑学家、数学家丘奇(A. Church,1903-1995)的Lambda演算模型[4,5,6]，波兰裔美国逻辑学家、数学家波斯特(E.L. Post,1897-1954)的Post机模型[7]，英国逻辑学家、数学家图灵(A.M. Turing,1912-1954)的图灵机模型[8]。虽然这些有关“计算”的模型是由不同逻辑学家各自独立提出的，但是经过研究发现，所有这些模型在“可计算”意义下都是等价的，亦即，在某个模型下“可计算”的问题，在另一个模型下也是“可计算”的。如此，逻辑学家们一致认为，这些模型不约而同地，恰如其分地表达了“基于有穷观点的能行方法”，亦即，“计算”这个抽象概念。另一方面，1935-1936年，丘奇和图灵各自独立地证明，在假定了所谓能行可计算就是图灵机可计算或者等价地说就是Lambda演算可计算的情况之下(该假定如今被称为“Church-Turing thesis”)，“基本问题”的一般形式是不可能的，亦即，不存在一种基于有穷观点的能行方法，它能够被用来判定任何一个给定的形式命题的真假，或者说，一定能够找到一个形式命题，其真假是不可能用某种基于有穷观点的能行方法判定的[4,5,8]。

通俗地说，基于有穷观点的所谓“计算”，就是每个演算步骤的下一步骤都必须是确定的、并且在有限步骤内可以给出最终结果的一个演算过程；基于有穷观点的所谓“可计算”，就是一定能够找到这样一个由有限步骤构成的演算过程。针对某个具体的计算问题，如果能够找到给出其最终结果的一个演算过程的清晰描述，那么我们说找到了解决该问题的一个算法，并且说该问题是“可计算”的；如果能够确切地证明不存在一个演算过程能够给出其最终结果，那么我们说对该问题的解决不存在一个算法，并且说该问题是“不可计算”的。在现今的计算机科学领域，当不加修饰地说到“计算”或者“可计算”时，就是指上述基于有穷观点的“计算”或者“可计算”，毫无例外。

上述基于有穷观点的“计算”或者“可计算”是一个极其一般的抽象概念，这一点从最直观的图灵机模型就可以看出来（图灵创建图灵机模型的基本想法很直观，模拟人用笔在纸上演算的过程）。因此，基于有穷观点的“可计算”所表达的“计算能力”是极其强的，在这几个模型之后又提出的基于有穷观点的“计算”模型的“计算能力”，也都没有超过它们。可以说，即便是今后还有新的计算模型提出，只要是遵守有穷观点的，其“计算能力”也不会超过1936年就已经提出的这几个计算模型了。

但是，另一方面，请注意，上述基于有穷观点的“计算”，并不是“计算”这个抽象概念的绝对的科学定义。能否一般地定义“计算”，如何定义“计算”，本质上是逻辑哲学或者数学哲学的问题。实际上，即便是在20世纪30年代基于有穷观点的“计算”概念已经被学术界普遍接受之后，也仍然有基于其它观点的“计算”概念被提出来，在此就不深入讨论了。

基于有穷观点的“可计算”概念仅仅涉及到在有限演算步骤内能否完成演算过程给出最终计算结果，并不关心一个具体演算过程实际上到底需要多少个演算步骤才能完成的问题。因此，这种“可计算”概念仅仅具有理论上的意义而对于“实际计算”几乎没有指导意义。一个可以在数百步甚至数万步演算能够计算出结果的“可计算”问题，与一个需要数亿步、数百亿步、数万亿步演算才能够计算出结果的“可计算”问题，在实际应用的意义下应该是完全不同的。

我们来看一个有关“可计算”问题所需演算步骤的数量化比较。我们考虑A,B,C三个“可计算”问题，假设为了算出最终结果A问题需要n步演算、B问题需要n2（n的2次方）步演算、而C问题需要log2n（以2为底n的对数）步演算，并且还假设这些问题在某种现代通用计算机上被实施计算时每个演算步骤花费的时间为0.001秒，那么关于这三个问题之演算步骤及花费时间的一个数量化对比如下：

由上面这个表我们可以看出，以30(36)步和0.03(0.36)秒为基准，三个问题之间的差距是巨大的。

在计算机科学中，一个基础理论领域是“计算复杂性理论”；该理论试图清晰地定义一些精细的衡量尺度，以它们为基本标准，把各种“可计算”问题及其算法按照其计算所需步骤数（时间复杂性）或者所需空间大小（空间复杂性）来进行分类，从而在众多问题和算法中引入计算复杂性的层级结构。

比如，上述三个例子中，问题A属于线性时间复杂性类问题（其解决算法也属于线性时间复杂性类算法，以下类推），问题B属于多项式时间复杂性类中2次多项式子类问题，问题C属于对数时间复杂性类问题。一般来说，在实际规模应用中可以接受的算法最多是2次多项式时间复杂性类的，3次多项式时间复杂性类问题及其算法在实际规模应用中就很难接受了。

最后，简单陈述一下“计算机”与“计算”的历史关系。如前所述，现代通用“计算机”和抽象“计算”理论是在20世纪30-40年代各自分别独立地发展起来的，原本的初始动机互不相干。但是，通过图灵和匈牙利裔美国数学家冯·诺依曼(John von Neumann,1903-1957)，使得原本独立的这两件事情有了联系。

现在世界上被一般认可的事实[9-12]是，图灵本人曾经为英国国家物理实验室(NPL)的ACE(Automatic Computing Engine)计算机研制计划写过一份开发提案书并且在其中专门提到该提案书应该与冯·诺依曼关于EDVAC的报告[13]一并阅读；图灵于1947年9月参加了英国曼彻斯特大学数学系的Mark I计算机研制项目并负责程序设计方面的工作。另一方面，冯·诺依曼至少到1938年7月邀请图灵留在普林斯顿大学（图灵于1936年-1938年在普林斯顿大学丘奇的指导下做研究并取得博士学位）担任自己的助手时，就已经熟知了图灵关于图灵机及可计算性的工作；1938年以后，冯·诺依曼本人曾经多次在不同场合对多位朋友或者同事称赞过图灵和他关于图灵机及可计算性的工作。在冯·诺依曼1944年9月参加到已经进行到中期的宾夕法尼亚大学ENIAC计算机研制项目时，作为一个数学家，他当然不仅仅是从技术角度也是从科学角度来参与的，他应该充分认识到了图灵机作为“万能计算机”理论模型的价值。冯·诺依曼参与了ENIAC的后续计划EDVAC(Electronic Discrete Variable Calculator)计算机研制的讨论，并且在1945年6月，把EDVAC项目组成员们内部讨论的记录（当时都是军事机密）归纳成为一份有关EDVAC的报告草稿[13]，以其个人名义单独署名并私下把它流传开来;正是这份并未正式公开发表的草稿，在当时就引起了EDVAC项目组成员们的极大不满，也成为后来有关冯·诺依曼与现代通用计算机之关系的许多误传“神话”和争论的源头，并使得“冯·诺依曼系统结构”这个很不恰当的技术名词在世界上流传很久（世界计算机科学界早已不再正式使用“冯·诺依曼系统结构”这个名词，正是为了避免误解及对计算机系统结构实际贡献者们的不尊重）。在1946年发表的有关EDVAC的正式报告[14]中，署名者已经不是冯·诺依曼一人了。

关于上述历史事实的详情，有兴趣的读者请参阅本文参考文献[9-15]以及本文前篇“计算机与计算模式 (1) 何谓计算机？”中的参考文献。

参考文献

[1] D. Hilbert and W. Ackermann, “Grundzüge der theoretischen Logik,” Springer-Verlag, 1928(1st Ed.), 1938(2nd Ed.), 1949(3rd Ed.), 1959(6th Ed.).(in German)

[2] K. Godel, “Uber formal unentscheidbare satze der Principia Mathematica und verwander systeme,” Monatschefte fur Mathematik und Physik, 38, pp. 173-198, 1931. (in German)

[3] S.C. Kleene, “General Recursive Functions of Natural Numbers,” Mathematische Annalen, 112, pp. 727-742, 1936.

[4] A． Church, “An Unsolvable Problem of Elementary Number Theory,” American Journal of Mathematics, 58, pp. 345-363, 1936.

[5] A． Church, “A Note on the Entscheidungsproblem,” Journal of Symbolic Logic, 1, pp. 40-41, 1936.

[6] A． Church, “The Calculi of Lambda Conversion,” Princeton University Press, 1941.

[7] E.L. Post, “Finite Combinatory Processes – Formulation 1,” Journal of Symbolic Logic, 1, pp. 103-105, 1936.

[8] A. Turing, “On Computable Numbers, with an Application to the Entscheidungsproblem,” Proceedings of the London Mathematical Society, Series 2, 42, pp. 230-265, 1936, Series 2, 43, pp. 544-546，1937.

[9] B. Randell, “On Alan Turing and the Origins of Digital Computers,” Machine Intelligence, 7, pp. 3-20, Edinburgh University Press, 1972.

[10] B. Randell, “The COLOSSUS,” in N. Metropolis, et al. (Ed.), “History of Computing in the Twentieth Century,” Academic Press, 1980.

[11] C. Petzold, “The Annotated Turing: A Guided Tour through Alan Turing’s Historic Paper on Computability and the Turing Machine,” Wiley, 2008.

[12] 星野力，“是谁，如何创造了计算机？” 共立出版社, 1995 (日文).

[13] J. von Neumann, “First Draft of a Report on the EDVAC,” 1945, published in the IEEE Annals of the History of Computing, Vol. 15, No. 4, pp. 27-43, 1993.

[14] A.W. Burks, H.H. Goldstine, and J. von Neumann, “Preliminary Discussion of the Logical Design of an Electronic Computing Instrument,” Institute for Advanced Study, Princetion, 1946. (in [15])

[15] B. Randell (Ed.), “The Origins of Digital Computers,” 3rd Edition, Springer-Verlag, 1982.