图灵指出：“我希望数字计算机能够最终激起人们对符号逻辑的极大兴趣……人与这些机器的交流的语言构成了一种符号逻辑。”[1]（Ｐ122）图灵所暗示的就是：程序设计语言不过是一种逻辑语言，而程序（或称算法）不过是用该语言表示的一列推理规则。蒯因也曾写道：“证明理论中的基本概念与机器计算理论中的基本概念相一致……（使得）关于数学证明的纯理论与关于机器计算的技术理论在底部合二而一。”[2]（Ｐ41）但是，逻辑和计算究竟是如何关联的？本文主要从逻辑学演进的角度探讨这一问题，并简要介绍我们的相关工作。
一、莱布尼兹： 推理和计算都是符号演算
对逻辑推理的形式化处理可以追溯到亚里士多德。早在公元前350年，亚里士多德就通过对各种推理模式的分析，提出了三段论。它曾一度被认为是推理的唯一逻辑范式，即使现在，它也是逻辑的重要组成部分。现在看来，亚里士多德的贡献还在于，人们可以把推理看成是对符号的操作。不过，最早看到这一点的应当是莱布尼兹，在他青年时期，数学研究迅速发展，处理代数表达式的方法已经系统化。笛卡尔和费马的工作表明，通过引入直角坐标系，可以把几何还原为代数。特别是，莱布尼兹（与牛顿）独立地创立了微积分，并成功地引入微积分运算符号，使得人们能够很容易地理解微积分。这些成功范例，激发了莱布尼兹建立一个通用语言的信念，寻找一个可以表达人类思想的符号系统，其中每个符号都以一种自然的方式表示一个确定的概念，进而发展出一种语言以及操纵这些符号的工具，使得仅凭符号演算，就可以确定用这种语言写成的哪些句子为真。莱布尼兹或许把人类所有的思维活动（包括推理与计算）都看成了符号演算。
二、布尔：逻辑推理即代数运算
布尔早期只是把代数方法应用于那些被称为微分算子的对象上，苏格兰逻辑学家威廉·哈密尔顿与德·摩根之间的一场争论，使得布尔的思想灵光闪现，即逻辑关系也许可以表示成一种代数。如果用x,y表示两个类，布尔就用xy表示既在x中又在y中的对象的类，显然应该有xx=x。布尔用记号xy暗示普通代数中的乘法，于是只有当x为0或1时，xx=x才成立。进而，布尔用x+y表示或在x或在y中的对象的类， 1-x表示不在x中的对象，从而x+(1-x)=1。下面我们通过一个例子来看布尔是如何把推理转换成代数运算的。我们知道如下是一个有效的三段论的例子：
这个三段论是有效的， 即无论x,y,z被代之以什么样的性质，只要前提是真的，结论就一定是真的。那么如何证明这是有效的呢?布尔是这样做的：说所有x都是y，即指x的每个东西都属于y，因而可表示为x=xy。类似的，所有的y都是z可以表示成y=yz。从而x=xy=x(yz)=(xy)z=xz, 即所有的x都是z[3]（P37）。
三、弗雷格：一个真正的符号演算系统
布尔的工作表明逻辑可以成为一个数学分支。在弗雷格看来，这是用逻辑来发展逻辑，产生了循环。因此，弗雷格认为，他的逻辑系统是不能用逻辑来发展的，而是要采用精确的语法规则或句法规则把他的概念文字发展成一种人工语言，进而把逻辑推理表示为机械的演算——即推理规则，这就是所谓的形式系统。1879年，弗雷格出版了他的小册子《概念文字》，副标题就是“一种模仿算术语言的纯思维的形式语言”，其中完善地发展了一阶逻辑系统（通常记作FOL）。FOL揭示了，人的演绎推理过程是连续执行某些简单的推理规则的过程。我们只需注意规则的执行，而无须理解各种符号的含义。哥德尔1930年的博士论文证明了弗雷格的规则是完备的，这就表明，弗雷格是第一次给出了能够解释人的所有演绎推理的形式系统。
弗雷格认为一阶逻辑只是朝着他的目标迈进的第一步。在19世纪，人们已经把数学基础研究归结到了为自然数理论提供基础。弗雷格希望为自然数理论提出一种纯逻辑的理论，进而证明算术、实数理论、微积分乃至整个数学都可以被看做逻辑的分支，这就是被后人称之为逻辑主义的观点。弗雷格关于算术基础的著作阐述了如何利用他所提出的逻辑发展算术理论。弗雷格的思想是把自然数看成集合的“集合”，例如，3这个数等同于所有恰含有3个元素的集合的“集合”。然而在1902年，正当弗雷格的《算术基础》第二卷马上就要出版时，他收到了英国哲学家罗素的信，信中指出了弗雷格的系统是矛盾的，这就是著名的罗素悖论。这对弗雷格来说是一个沉重的打击，可他不得不接受这个现实，直到1925年去世，他都认为自己的工作毫无结果。更不幸的是，弗雷格的工作当时也不为同事们所认同，所以他从未晋升为正教授。虽然如此，弗雷格的工作还是产生了深远的影响，他的《概念文字》被后人誉为“也许是自古以来最重要的逻辑学著作”[4]（Ｐ1）。后来的皮亚诺算术系统被认为是算术理论的形式化，集合论公理系统（如Zermelo-Frankel系统）被认为是数学的基础。这些形式系统使得通过符号演算来实现数值运算和推理成为可能。
四、哥德尔：符号演算与算术运算
在弗雷格看来，逻辑原则总是永真的，因而建立在其上的数学定理也总是永真的，只可惜弗雷格的努力失败了。后来罗素等人继承了弗雷格的思想。然而他们毫无顾忌地使用无穷对象，这遭到了以布劳维尔为代表的直觉主义者的批判。同时罗素等人把某些原则（如无穷公理）看成是逻辑原则的思想也不能被多数人所接受。一方面，希尔伯特不能容忍直觉主义者把无穷对象从数学中驱逐出去；另一方面，通过研究罗素和怀特海的《数学原理》，希尔伯特也认为弗雷格和罗素的方法是行不通的。不过， 希尔伯特仍认为建立数学和逻辑的形式系统是十分重要的，但他区分了形式系统的“内部”和“外部”。从内部来看，它就是数学，各种数学计算和推理都可以进行，且每一种数学方法都可以不加限制地应用，但从外部看，它不过是一些公式和符号的操作，这些操作可以在无须考虑意义的情况下进行演算，那么最重要的任务就是证明形式系统是无矛盾的。为了回应直觉主义者的批评，希尔伯特要求，当从外部研究形式系统时，所有的方法必须遵从所谓的“有穷性”，无矛盾性的证明应该是在形式系统外部完成，这样，就可以“在直觉主义的基础上把古典数学建立起来”[５]（P168）。
哥德尔的不完全性定理宣告了希尔伯特计划的破产。哥德尔的编码在他的不完全性定理的证明中起着举足轻重的作用，同时也使我们看到，符号演算也可转化成算术运算。例如，在皮亚诺算术系统中，首先对其中的每一个符号进行编码，如下表：
五、图灵机：一个计算模型
实际上，莱布尼兹的梦想可分为两部分：首先把人类的思维活动还原为符号演算，然后，设计制造强大的计算设备来执行这些演算。莱布尼兹本人曾于1673年访问伦敦时展示了一个能执行加减乘除运算的机器（之前的帕斯卡的机器只能进行加减运算）。之后，莱布尼兹还描述了一种能解代数方程的机器。然而，在建立“通用语言”的梦想实现之前，奢望实现莱布尼兹梦想的计算机是不现实的。到了1879年，弗雷格第一次给出了包含所有的演绎推理的符号演算系统，从而实现了莱布尼兹所憧憬的通用语言。那么，莱布尼兹梦想的计算设备是否存在呢？用希尔伯特话来说即是：是否存在一个这样的计算程序，只要给定用一阶语言写出的任意两个公式A和B，那么通过这个程序总是可以判定，弗雷格的规则是否足以保证能够从A推出B？这个问题后来被称做希尔伯特的“判定问题”。
有些数学家凭自己的直觉对希尔伯特“判定问题”作了否定的回答。例如剑桥大学的哈代曾评论说：当然不存在这样的算法，否则，我们就可以用一套机械的规则来解决一切数学问题，数学家的活动也将寿终正寝了[3]（P164）。特别是在哥德尔证明不完全性定理之后，人们更不相信希尔伯特所设想的算法是存在的。图灵则思考如何证明它的不存在性。
通过弗雷格的一阶逻辑使我们对推理过程有了清晰的认识。推理过程就是从前提出发不断使用几个简单的推理规则，最后得出结论的过程。那么什么是计算过程呢？我们可想象中小学生是如何作算术运算的。只要掌握了个位数的加法，我们就有一套方法来求任意两个数的和，甚至可以计算出任意多个数的和。进一步，只要我们掌握了个位数的乘法，就可有一套方法计算出任何两个数的积。实际上，复杂的算术运算被分解成若干步骤，每一步我们进行的都是简单的工作（如移位、个位数加法或乘法等）。但我们必须清楚每一步该做什么——这就是所谓的心灵状态，图灵正是这样来分析计算过程的，他设计一种现在被称为图灵机的装置。图灵机包括一条纸带、一个读写头和一个状态控制器来指示当前所处的状态。图灵机只能执行4个基本操作：左移、右移、读、写。我们必须指明当图灵机处于什么状态、读到什么符号时它应该执行怎样的操作，比如：
当机器处于状态R, 读写头所在的方格中的符号为a时，把符号b写入该方格，然后向右移动一个方格，并转到状态S。
上面描述的实际是一条指令，程序就是有穷多条指令组成的集合，所谓计算，指的就是图灵机按照程序的运行过程。简单地说，称一个函数是图灵机可计算的，如果有一个程序来计算这个函数。进而，图灵利用康托对角线方法证明了不存在希尔伯特所设想的判定程序。不过，图灵想不到的是，在他研究“判定问题”的过程中，普林斯顿大学的丘奇也得出了类似的结论。丘奇发表在《美国数学杂志》的文章“一个不可解的初等数论问题”提及了两个可计算性的概念：一个是?姿-可定义函数的概念，一个是一般递归函数的概念。这两个概念实际上是等价的。图灵很快证明了，?姿-可定义性与他的可计算性也是等价的。1936年，美国逻辑学家坡斯特提出了产生式系统，产生式系统导出的函数恰好就是图灵可计算函数。因此丘奇和图灵提出了他们的论题：即直观的能行可计算函数等都是图灵机可计算函数（λ-可定义函数）。
图灵对计算的分析（以及丘奇-图灵论题）使得我们对计算的本质有了清晰的认识：计算过程就是从输入的符号开始执行一系列基本操作得到另一个符号串的过程。再来回顾我们对推理的认识：推理就是从前提开始连续使用简单的推理规则得出结论的过程。不难发现，二者是多么的相似。实际上，使用推理规则的过程都可以通过执行一系列基本操作来完成。而图灵机所执行的基本操作也可以由推理来完成（见哥德尔的表示定理）。因此，我们有理由认为，推理和计算本质上是一个概念，换句话说，计算可以由推理来完成，推理也可以转化为计算。
六、新的计算模型研究
通用图灵机是现代电子计算机的理论模型，图灵机的基本操作是通过电子线路来实现的。但是，图灵对计算的分析使我们认识到，不管什么装置，只要它能执行某些简单的操作，并且有办法控制这个装置使得它在相应的状态下执行相应的操作，那么这个装置就可以进行计算。我们也可以称它是计算机。
1994年11月，美国计算机科学家阿德勒曼(L.Adleman)在美国《科学》上公布DNA计算机的理论，并成功运用DNA计算机解决了一个有向哈密顿路径问题。在双螺旋的DNA中，分子链是由互补的核苷酸配对组成的，两条链依靠氢键结合在一起。由于氢键键数的限制，DNA的碱基排列配对方式只能是A对T或C对G。这样，DNA分子链就可以用来表示信息。我们可以通过不同的酶对DNA分子链进行剪切、连接、复制等简单操作，DNA计算就是通过酶对DNA分子链进行一系列的操作[6]（Ｐ１６）。不过，目前DNA计算机能够处理的问题，还仅仅是利用分子技术解决的几个特定问题，通用DNA计算机的理论模型至今还未建立。
引起计算方式重大变革的远不止DNA计算机。细胞自动机、神经网络、光学计算机、量子计算机、蛋白质计算机等新型计算机模型层出不穷，随着科学的不断发展，还可能会出现更多计算模型。
然而，就可计算性而言，所有这些计算模型都与图灵机是等价的，也就是说，凡是这些机器能够计算的，图灵机也可以计算，反之亦然。那么研究这些新的计算机又有什么意义呢？
首先，所有这些计算模型都是等价的事实说明，由丘奇—图灵论题所揭示的计算的本质是普适的。其次，从不同的观点出发，提出的计算模型却是等价的，这一事实促使不同观点的相互融合。例如，联结主义认为，人类的认知是从大量并行的神经元的相互作用中产生的。因此联结主义不是以符号演算来模拟认知过程，而是通过神经网络来模拟发生在神经系统中的过程。不过，坡拉克（J.Pollack）于1987年证明了，神经网络与图灵机只是形式上的差别，二者是等价的。最后， 寻找新的计算模型是为了制造更加高效的计算机。例如，量子并行操作技术使得量子图灵机能在同一带上将大量的输入信号进行编码并同时对它们进行演算，从而增强运算能力。
我们与国外学者合作提出量化逻辑的模型理论，这一理论使得我们在量化逻辑推理的计算复杂性研究方面取得了突破。对于度量空间紧集及其算子，我们提出了新的表示方法和新的计算模型，这为分析它们的计算复杂性提供了理论工具[7](P３８５－４０２)。
参考文献
[1] A. TURING.Collected Works: Mechanical Intelligence[M]. North-Holland, 1992.
[2] W. V. QUINE. The Ways of Paradox and Other Essays[M]. Random House, 1966.
[3] MARTIN DAVIS. Engines of Logic Mathematicians and the Origin of the Computer[M]. W. W Norton Press, 2000.
[4] VAN HEIJENOORT. From Frege to Goedel[M]. Harvard University Press, 1967.
[5] P. MANCOSU. From Brouwer to Hilbert[M]. Oxford University Press, 1998.
[6] P. CLOTE, R. BACKOFEN. Computational Molecular Biology[M]. John Wiley & Sons Ltd, 2001.
[7] XISHUN ZHAO, NORBERT MUELLER. Complexity of Operators of Compact Set[Z]. International Conference on Computability and Complexity in Analysis , Siena, 2007.
[责任编辑 李小娟付洪泉]
“本文中所涉及到的图表、公式注解等形式请以PDF格式阅读原文。”