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

何谓“计算”？-- 可计算性理论简介 

程京德

人类历史上第一次清晰地定义抽象概念“计算”，是在现代数理逻辑领域中试图回答由希尔伯特(David Hilbert,1862-1943)提出的数理逻辑基本(主要)问题“希尔伯特判定问题(Hilbert’s Entscheidungsproblem)”的过程中完成的。希尔伯特判定问题是由希尔伯特20世纪20年代初首先在其讲演中提出，并在希尔伯特和阿克曼(Wilhelm Ackermann,1896-1962)的著作[1]中给出清晰陈述的：

“给出一个判定过程，它允许人们通过有限次数的运算来判定任意一个给定（一阶谓词– 笔者注）逻辑表达式的普遍有效性(或者其否定的可满足性，希尔伯特和阿克曼把这两个等价的判定问题统称为判定问题 - 笔者注) (It was to give a decision procedure(Entscheidungsverfahren)‘that allows one to decide the validity (respectively satisfiability) of a given logical expression by a finite number of operations’[1,1928(1st Ed.), pp.72-73])”[2]。希尔伯特和阿克曼将此问题称为“数理逻辑基本(主要)问题(the fundamental(main) problem of mathematical logic)”[1,2]。

“希尔伯特判定问题是，发现一种方法，对于任意一个给定一阶谓词逻辑式，它可以通过有限次清晰定义的能行步骤判定该公式是否是普遍有效的(Hilbert’s Entscheidungsproblem was to provide a method that would, given a formula of first-order logic, determine in a finite unmber of well-defined effective steps whether or not that formula is valid) 。”[3] 

希尔伯特在1899年给出了几何的抽象公理化[3]，并在1900年表明几何的一致性问题可以归结为实数系统的一致性问题，进而可以通过利用戴德金(Julius Wilhelm Richard Dedekind,1831-1916)的结果归结为算术的一致性问题。1900年在巴黎举行的第二次世界数学家大会上希尔伯特提出的数学问题中的第二个问题，就是算术公理的一致（相容）性问题[5]。希尔伯特1904年在海德堡举行的第三次世界数学家大学上提出基于有穷观点来证明算术的一致性[6]，从而形成其著名的“希尔伯特计划(Hilbert's program)”[7,8]。 

希尔伯特计划试图通过一系列基础（形式化）工作来奠定数学的基础，使得数学在形式化基础上是一致的、无矛盾的；更准确地说，希尔伯特希望用形式化公理方法来形式化所有数学，并以基于不假定实无穷的有穷观点的能行方法来证明数学公理是一致的。这样就可以保证从数学中排除那些已知的悖论，而且还保证建立在形式化基础之上的数学根本不可能出现悖论。“希尔伯特计划”中的重要工作之一就是解决希尔伯特判定问题，因为数学的形式公理化需要精确的逻辑形式。正是对希尔伯特判定问题中要求的所谓“基于有穷观点的能行方法”的认识和形式化工作，导致了对抽象概念“计算”的认识和建立,从而解决了该问题（无论从哲学上还是从数学上来说，要证实某个“事情”是不可能的或不存在的，必须先认识并定义清楚该“事情”是什么）。丘奇(Alonzo Church,1903-1995)在1935年，图灵(Alan Mathison Turing,1912-1954)在1936年各自独立地以不同的方法给出了否定回答，希尔伯特判定问题谋求的一般判定方法是不存在的。

由上述历史背景可知，所谓“计算”，本质上是一个逻辑学家和数学家为了建立和研究经典数理逻辑从数学领域内的需要出发而提出并且定义的一个抽象概念，提出和定义“计算”的初始动机与现实世界中人类的“日常计算”毫不相干，也与人类用来辅助日常计算的“计算工具”（比如算盘，计算尺，手摇计算机等）以及谋求让日常计算机械化、自动化的“计算机”（比如巴贝奇(Charles Babbage,1791-1871)的齿轮计算机）毫不相干。但是，正是数理逻辑学家们对抽象概念“计算”的定义和形式化，对“计算”的抽象数学模型的构建，尤其是图灵的抽象数学模型“图灵机”的提出，才为“通用计算机”的实现提供了坚实的理论基础，使得“计算”的高速自动化以现代电子数字计算机的方式得以实现。

在20世纪30年代，为了解决希尔伯特判定问题和形式化“基于有穷观点的能行方法”，几位逻辑学家几乎同时各自独立地提出了几个关于“能行可计算(effectively calculable)”的抽象数学模型来形式地表达“基于有穷观点的能行方法”。其中有：奥地利逻辑学家哥德尔(Kurt Friedrich Gödel,1906-1978)和美国逻辑学家克莱尼(Stephen Cole Kleene,1909-1994)的递归函数模型[9,10], 美国逻辑学家丘奇的Lambda演算模型[11-13]，波兰裔美国逻辑学家波斯特(Emil Leon Post,1897-1954)的Post机模型[14]，英国逻辑学家图灵的图灵机模型[15]。

虽然这些有关“计算”的抽象数学模型是由不同逻辑学家各自独立提出的，但是经过研究发现，所有这些基于有穷观点的模型在“可计算”意义下都是等价的，亦即，在某个模型下“可计算”的问题/函数，在另一个模型下也是“可计算”的；在某个模型下“不可计算”的问题/函数，在另一个模型下也是“不可计算”的。如此，逻辑学家们一致认为，这些抽象数学模型不约而同地，恰如其分地表达了“基于有穷观点的能行方法”，亦即，“计算”这个抽象概念。另一方面，1935-1936年，如前所述，丘奇和图灵各自独立地证明，在假定了所谓“能行可计算”就是“Lambda演算可计算”或者等价地说就是“图灵机可计算”的前提之下(该假定如今被称为“Church-Turing thesis”)，“希尔伯特判定问题”的一般性解决是不可能的，亦即，不存在一种基于有穷观点的能行方法，它能够被用来判定任意一个给定的一阶谓词逻辑式的普遍有效性[11,12,15]。

下面让我们来简单地介绍一下图灵机。

上图显示了我们人类在进行“计算”时，参与“计算”的各种要素。图灵就是根据这些要素设计了他的计算模型：图灵机。物理地、直观地说，一台图灵机有一条无限长的带子，带子上被划分为一个一个的格子，每个格子里可以写入一个字符。图灵机还有一个读写头可以从带子上读出或者写入字符。带子和读写头之间有相对运动，每次运动移动一个格子位置。图灵机还有一个控制装置用来决定读写及相对运动。如下图(来自Wiki)所示：

在图灵机进行“计算”前，在其带子上预先放置若干字符构成的问题/函数。开始工作后，图灵机根据控制装置发出的指令不断地运动并对其带子上的字符进行读写操作直到“计算”结束停下来（意味着被“计算”的问题/函数是“可计算（可判定）”的），或者不停地一直工作下去（意味着被“计算”的问题/函数是“不可计算（不可判定）”的）。

数学形式化地、抽象地定义，一台图灵机是一个7元组(Q, Σ, Γ, δ, q₀, q_accept, q_reject)：Q是一个状态号的有穷集合，Σ是不可包含空白符的输入字符有穷集合， Γ是必须包含空白符的字符有穷集合，δ =_df ((Q − {q_accept, q_reject}) X Γ) --> ((Q X Γ) X {L, R}) 是一个全函数，叫做状态转移函数，q₀是初始状态号， q_accept是接受状态号， q_reject是拒绝状态号，q_reject !=  q_accept。

图灵机的状态转移函数所表达的一次状态转移（函数的一个有序对），(q_i, a_j) --> (q_i+1,a_j+1, L|R) ((q_i, a_j), (q_i+1, a_j+1, L|R))，意味着图灵机从当前的状态号q_i和当前字符a_j转移到状态号q_i+1并且写下字符a_j+1，然后向左(L)或者向右(R)运动一格。

图灵机的当前状态号，带子上当前的字符串内容，以及读写头的当前位置，这三者构成图灵机的一个当前格局。图灵机在状态转移函数的控制下从一个格局转移到另一个格局，一个格局的有穷序列（最后格局的状态号是接受状态或拒绝状态）就表达了一个“可计算（可判定）”问题/函数的“计算”过程，一个格局的无穷序列就表达了一个“不可计算（不可判定）”问题/函数的“计算”过程。

支撑整个计算机科学的最基础的理论，可计算性理论(computability theory)，就是定义“计算”的各种抽象数学模型，并且讨论在各个模型下各种问题/函数的“可计算（可判定）”性质。

必须申明的一点是，可计算性理论讨论的是在（可计算性理论观点）原理上是否可计算（可判定）的问题，一个原理上可计算（可判定）的问题，从计算所需时间或所需空间的观点上来看未必是实际上合理地可计算（可判定）的。计算复杂性理论(computational complexity theory)讨论原理上可计算（可判定）问题所需资源多少的课题。

上述基于有穷观点的“计算”或者“可计算（可判定）性”是一个极其一般的抽象概念，这一点从最直观的图灵机物理模型就可以看出来。因此，基于有穷观点的可计算（可判定）性所表达的计算能力是极其强的。在本文前述几个抽象数学模型之后又提出的基于有穷观点的计算模型的计算能力，也都没有超过它们。可以说，即便是今后还有新的抽象数学模型提出，只要是遵守有穷观点的，其计算能力也不会超过1930年代就已经提出的这几个模型。

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

最后，从“计算”的角度陈述一下笔者关于人类智能和人工智能的观点。从数理逻辑学家们认识和定义“计算”，根据有穷观点提出各种抽象数学模型来形式化地定义可计算（可判定）性，构建内容丰富的可计算性理论，我们可以看到人类学者通过有穷手段去驾驭无穷的智力/智能之伟大（另外一个可举出的例子是现代公理集合论，在那里，“无穷”更是直接研究对象）。在笔者看来，人类智力/智能之伟大的本质在于人类的高度概念抽象能力，只要人类还生存在这个世界上，这种高度概念抽象能力就是永无止境的。另一方面，所谓“人工智能”，只要是“人工”，应该就不可或缺地使用计算机的“计算”能力。而可计算性理论（再加上计算复杂性理论）已经非常清楚地划定了计算机（“孙悟空”）所能“计算”问题的范围（“如来佛手掌”）。因此，担心人工智能会有一天超越人类智能，根本就是杞人忧天！

参考文献

[1] D. Hilbert and W. Ackermann, “Grundzüge der theoretischen Logik,” 1928(1st Ed.), 1938(2nd Ed.), 1949(3rd Ed.), 1959(6th Ed.), Springer-Verlag (in German). 
English translation: “Principles of Mathematical Logic,” AMS Chelsea Publishing, 1950 (translation of the 1938 second edition). 
中译(莫绍揆译): “数理逻辑基础”(第三版)，1958.
Book review: C. H. Langford, “Hilbert and Ackermann on Mathematical Logic,” Bulletin of the American Mathematical Society, Vol. 36, pp. 22-25, 1930.
Book review: H. B. Curry, “Hilbert and Ackermann on Mathematical Logic,” Bulletin of the American Mathematical Society, Vol. 59, pp. 263-267, 1953. 

[2] R. I. Soare, “The History and Concept of Computability,” in E. R. Griffor (Ed.), “Handbook of Computability Theory,” Elsevier, 1999. 

[3] M. Davis, “Engines of Logic – Mathematics and the Origin of the Computer,” W.W. Norton, 2000. 中译(张卜天译):“逻辑的引擎”，2005.

[4] D. Hilbert, “Grundlagen der Geometrie,” Teubner, 1899 (in German). 

[5] D. Hilbert, “Mathematische Probleme,” Nachrichten von der Königlichen Gesellschaft der Wissenschaften zu Göttingen, Math.-Phys. Klasse, pp. 253–297，1900 (in German) (Lecture Delivered before the International Congress of Mathematicians at Paris in 1900) 

[6] D. Hilbert,“über die Grundlagen der Logik und der Arithmetik”, in Verhandlungen des dritten Internationalen Mathematiker-Kongresses in Heidelberg, 1904 (in German). 

[7] R. Zach, “Hilbert’s Program,” Stanford Encyclopedia of Philosophy, 2003,2019.

[8] 王宪钧, “数理逻辑引论 第三篇 数理逻辑发展简述”，北京大学出版社，1982, 1998. 

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

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

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

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

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

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

[15] 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.