非原创，转载，学习用，勿侵权。
想要有一套机械规则来判断每个命题的真假，让人类不用再费脑筋进行思考，让任何一个人只要熟练运用这套规则就能变聪明，这是一个美好的梦想。
希尔伯特认为数学就是形式符号的游戏，数学符号并不代表任何东西，它们只是符号，数学命题只不过是字符串。
图灵认为，图灵机已经把握住了所有计算的本质，任何计算都无法超出图灵机的范围，也就是说，不论多复杂的计算过程，只要它是机械的算法，那就一定能找到一个图灵机执行这个计算过程。
简介
《逻辑的引擎》这本书，讲述了最「无用」的哲学和纯数学，导致了最「有用」的计算机科学的诞生。
今天我要给大家推荐的这本书，叫《逻辑的引擎》。看到这个书名，大家一定无法猜到它的内容是什么，不过它的英文原版名称就很好理解了——《Engines of Logic: Mathematicians and the Origin of the Computer》，翻译过来就是：《逻辑的引擎：数学家与计算机的起源》。这本书讲的，实际上是计算机科学这一门非常年轻的学科，究竟是如何从数学家们的逻辑研究中发端的。
对于哲学、理论数学这种理论性的学科，许多人常常觉得它们是「无用」的，备受推崇的往往是统计学、计算机等学科。当然，也有人同意理论学科大有用处，因为它们能「指导」其它的学科，具有前瞻性，但是如果请他们举一个具体的例子出来，很多人却答不上来。针对这种情况，《逻辑的引擎》这本书就提供了一个很好的实例，让我们看到，最「无用」的哲学和纯数学，竟然导致了最「有用」的计算机科学的诞生。
本书作者马丁·戴维斯，是计算机科学发展史上的先驱人物，美国艺术与科学院和美国数学学会成员，他在本书的引言和前言中如此说道：「当前，正当计算机技术以惊人的速度前进时……我们很容易忘记那些逻辑学家，正是他们的思想使得这一切成为可能」，「我将讲述这些人的生活故事，并解释他们的部分思想。我希望读者们……对抽象思想的价值，多一份敬意。」
虽然本书讲的是计算机的起源，但没有相关背景的读者无需担心，阅读本书不需要任何专业背景知识，并且由于书中穿插了很多名人轶事，读者一定不会感到枯燥。另外，本书的译者张卜天老师也非常值得推荐，他的每一本译著都广受好评，涵盖哲学、逻辑学、科学史甚至拉丁语教材，对这些「无用」的领域感兴趣的读者，建议不要错过他的任何一本书。
上面介绍了这本书的基本情况和内容，现在我正式开始解读这本书。我将从3个部分进行。第一部分，莱布尼茨之梦，与现代逻辑之父弗雷格的符号逻辑研究；第二部分，20 世纪最杰出的数学家希尔伯特和符号游戏；第三部分，图灵，算法和图灵机。
下面进入到第一部分。当我们观察整数的算术计算，比如加减乘除时，不难发现，这些计算都是机械的操作。就连小学生，只要掌握了一套机械的计算步骤，也可以不用一点思考而算出结果。即使是高等数学中的微积分运算，我们也可以花几十块钱买一个科学计算器，计算器可以根据既定的机械程序算出结果。这些数学工作似乎不需要动脑即可完成。我们不禁设想，不止这种简单的等式计算，人类的一切知识，是否也都能通过一个类似的机械步骤来判断？如果真的能，那么这个世界将会减少很多无意义的争论，争论双方都冷静下来按规则做计算就够了。 想要有一套机械规则来判断每个命题的真假，让人类不用再费脑筋进行思考，让任何一个人只要熟练运用这套规则就能变聪明，这是一个美好的梦想。在计算机科学如此发达的今天，提出这样一个梦想并不奇怪，但实际上，300 多年前已经有人提出这个梦想了，他就是莱布尼茨，一个大家都知道的数学家和哲学家。
为了实现这个梦想，莱布尼茨认为，首先需要把人类在所有领域的知识都用符号表示出来，就像算术符号以及他自己发明的微积分运算符号一样。每个符号都表示特定的含义，只有这样才能避免自然语言的模糊性和歧义，才有可能为知识建立一套机械的计算规则。他甚至还希望，在建立这套计算规则之后，能制造出相应的按规则进行计算的机器。当然，他并没有实现这个梦想，他甚至没有能够为这个梦想的实现作出任何实质性的贡献。莱布尼茨绝对无法想到，他的这个梦想将在百年后给世界带来怎样翻天覆地的变化，将吸引多少天才为之前赴后继。接下来我将为大家介绍其中的三个作出重要贡献的人物，他们是：现代逻辑之父弗雷格、20 世纪最重要的数学家的希尔伯特，以及计算机理论之父图灵。
德国数学家和哲学家弗雷格，是这些天才中最耀眼的一个，他被公认为现代逻辑之父，他的著作《概念文字》被誉为自古以来最重要的逻辑学著作。弗雷格发明了一套符号语言，这套语言成功地将人类的逻辑符号化。弗雷格还几乎成功地用他的符号逻辑体系推出整个代数学，可惜最后被罗素指出了他的体系中内在的矛盾，也就是著名的「罗素悖论」。但即便如此，时至今日，数学、计算机和哲学专业所学的逻辑——确切来说叫「一阶逻辑」——与弗雷格当初创立的，并没有什么不同。下面我们来看看弗雷格是如何研究符号逻辑，从而推动莱布尼茨之梦的实现。
弗雷格的符号逻辑研究，来源于他对语言和数学的哲学观念，也就是他的数学哲学观。先看这个问题：数学为什么是对的？通常来说，科学是可证伪的，科学理论可能被后来者推翻，但数学不会，已经证明了的数学定理即使在一千年后也还是对的。数学的这种正确性从何而来？证明一个复杂的数学定理要很多步骤，但说到底一个数学证明中只有两个元素：前提和推理规则。想要证明任何一个数学命题，都必须从前提出发，使用正确的推理规则，一步步得到结论。因此，数学结论的正确性，就依赖于前提和推理规则的正确性。整个数学有一些公共的前提，也就是定义和公理，它们是整个数学大厦的基石，问题在于，它们本身的正确性从何而来？对这个问题，弗雷格的观点是：数学的正确性来源于人类普遍的逻辑，而逻辑的正确性是不需要说明的，因为逻辑一定是正确的。这种观点叫「逻辑主义」，它认为数学的概念和定义能归结到最基本的逻辑术语上，对数学定理的推导也只需要最基本的逻辑规则。现在的问题是：逻辑规则是什么？
显然，逻辑规则就像一个函数一样，输入一些命题作为前提，输出一个命题作为结论。那么，什么是命题呢？命题内部有怎样的结构？命题和命题间的关系是怎样？这些就属于语言哲学的问题了，弗雷格对这些问题作出了前所未有的精彩回答。在弗雷格之前的哲学家，比如大家都听过的康德，认为命题就是一个判断句，判断它的主语具有谓语所说的那种性质，比如「4 是偶数」这个命题就是在判断 4 这个主语具有「能被 2 整除」这样一个性质。可是这种考虑未免太简单了，比如「所有偶数都能被 2 整除」这个命题，难道是说「所有偶数」这个主语具有这个性质吗？显然不是，因为「所有偶数」这个主语是一个集合，而集合显然不能被某个数字整除。再比如，「2 是奇数或是偶数」这个命题中，「或」这个词该怎么理解？弗雷格意识到，必须先搞清楚命题内部到底有什么成分。在他的著作《概念文字》中，他提出了好几个成分，然后按照莱布尼茨之梦，他把命题中的每个元素都用人工的字母和符号来表示，这样一来，命题就可以翻译成一个字符串。我们可以发现，弗雷格的做法已经很接近现代编程的思想了。这本《逻辑的引擎》给了很多具体的例子来展示如何把用日常语言表达的命题，翻译成弗雷格的符号语言。因为命题被翻译成了字符串，所以在弗雷格的体系中，一个逻辑规则其实就是说当我们有某些字符串时，可以推理出某个特定的字符串。
弗雷格差一点就成功地从他建立的逻辑体系中推出了数学中最基础的部分——算术。在弗雷格就快完成他的伟大工作时，罗素给他写了一封信指出，他为算术所建立的逻辑体系内部有矛盾，这就是罗素悖论。弗雷格接受了他失败的事实，之后他再也没有能够做出伟大的工作，而罗素却没有放弃，他发展了自己的体系，像弗雷格一样试图把数学还原到逻辑上。
莱布尼茨之梦要求的符号系统，需要满足两个条件。第一个条件是，它需要包含人类的一切知识。当然，现在看来，这肯定是没法达到了，自然科学的发展已经远远超出了莱布尼茨的想象，一个符号系统不可能包含所有科学知识；但如果仅仅限制在数学上，希望某个符号系统能推出所有数学，这还是有希望的。不过因为罗素悖论，弗雷格的符号体系并没有达到这个条件。莱布尼茨之梦的第二个条件是，这个符号体系要有一个机械的算法，能够自动判断体系内的某个命题是否正确。弗雷格的体系是否满足这个要求？弗雷格本人并不知道，在几十年后，图灵证明了不存在这样的算法。严格来说，图灵的证明并不是针对弗雷格的体系，而是针对我们接下来要介绍的数学家希尔伯特的体系。无论如何，因为弗雷格的这些工作，莱布尼茨之梦的实现迈进了一大步。
希尔伯特是我们要介绍的第二位天才人物，他和弗雷格是同一时代的人，被誉为 20 世纪最杰出的数学家。有人说，他是迄今为止最后一个在所有数学领域都有成就的人，不过我们今天只介绍他在数学基础方面的工作。
对于「数学是什么」这个问题，我们刚刚已经介绍过弗雷格的回答，弗雷格认为数学就是逻辑，这种观点被称为逻辑主义。希尔伯特并不同意这种观点，他认为数学其实就是纯粹的符号游戏，数学家们先创造各种奇奇怪怪的符号，规定这些符号的使用规则，然后按照这些规则来摆弄这些符号。这些符号代表什么？数学到底是研究什么的？希尔伯特认为，数学符号什么也不代表，数学的研究对象什么也不是。
举个例子，通常我们认为平面几何就是研究点、线、面之间的关系，比如「两点确定一条直线」。但什么是点、线、面？有人真正见过数学上的「点线面」吗？要知道数学上的点是没有大小的，线是没有宽度的，面是没有厚度的。所以，如果说「几何学研究点、线、面」，那这句话说的到底是什么意思？其实，即使我们用 A、B、C 三个字母分别替换点、线、面这三个字，也可以得到一系列几何学定理，比如把「两点确定一条直线」替换为「两 A 确定一条 B」，我们依然可以用这种替换后的语言来研究几何学，推出一系列几何定理。至于点线面或者 ABC 究竟代表着什么意思，并不重要。数学家无需关注数学语言的意义，也可以得到很多数学结论。
因此简单来说，希尔伯特对「数学是什么」这个问题的回答就是：数学就是形式符号的游戏，数学符号并不代表任何东西，它们只是符号，数学命题只不过是字符串。他的这种观点被称为「形式主义」。莱布尼茨坚信人类所有的知识都能被符号化，而希尔伯特坚信，人类所有的数学知识都可以被符号化。
希尔伯特不仅是这样相信的，他也是这样做的。他使用所谓的「符号系统」来完成这一目标。首先将数学中需要的一切概念，翻译为一系列的人工符号，这些符号通过特定的排列顺序可以组成命题，然后规定某些符号串是这一系统的公理，再规定可以从哪些符号串推出另一些符号串，也就是规定了系统的推导规则，这样一来，公理和推理规则就都有了，这一系统就可以不断地从公理出发，推出新的命题了。
这里有一个问题：既然形式主义认为数学只是纯粹的符号操作，并没有任何意义，那么符号系统是否可以随便定义？希尔伯特认为，这些符号系统至少需要满足无矛盾性，也就是说，系统不能推出两个互相矛盾的命题。就像后来一个数学家所说：「物理学研究现实的情况，数学研究任何逻辑上可能的情况。」只要不存在矛盾，任何情况都是逻辑上可能的。因此就算希尔伯特认为数学只是符号游戏，他也承认无矛盾性是必须满足的，这是数学的基础。
有了符号系统这个概念，并且知道符号系统最低的要求是不推出矛盾，这时希尔伯特就可以开始实行他对全体数学进行符号化的计划了。最终，为了完成莱布尼茨之梦，他需要证明这三点：
第一，所有的数学真理都能被他的符号系统推出；
第二，他的符号系统是无矛盾的；
第三，存在一个机械的算法，任意给一个数学命题，他的符号系统都能通过这一算法来判断这个命题是否推得出。
如果这三点都被证明出来，那么可以说，希尔伯特在数学方面真正实现了莱布尼茨之梦。有了这样一套算法之后，任何一个人只要会熟练运用这套算法，就能成为大数学家！
然而，他的梦想破灭了，这三点都被证明是不可能的。第一条，哥德尔不完备定理证明了，有些数学真理没法被它的符号系统推出。同样的，哥德尔通过不完备定理还推论出，希尔伯特不可能单凭符号系统就证明系统自己的无矛盾性，证明无矛盾性必须借助超出符号系统外的手段，因此数学不可能完全奠基在纯粹的符号系统上。对于第三条，是否存在一个算法可以判断命题的真假，这一问题在 1936 年被图灵解决了，答案仍然是否定的。
虽然这三点都被证明不可能，但希尔伯特对数学的贡献是巨大的。正是他对数学基础的哲学思考，导致了他巨大的数学成就，而图灵也正是在解决他遗留的问题时，发明了图灵机这一概念。没有图灵机就没有现代计算机，因此可以说，希尔伯特的哲学思考，间接导致了现代计算机的产生，思想的力量不可谓不伟大。
顺便说一句，哥德尔能证明出被称为 20 世纪最重要数学定理的哥德尔不完备定理，和哥德尔的哲学思想也脱不了干系。哥德尔坚信数学命题有它固有的真假，绝对不是像希尔伯特说的那样是无意义的符号串。他坚信，仅靠符号串不可能涵盖全部的数学知识，这种思想是他数学成就的来源。
现在来到了今天要介绍的第三位天才——图灵。图灵是大家都知道的人物，对计算机稍有了解的人不会不知道图灵机，它是一切现代计算机的鼻祖，图灵奖也是当代计算机领域最高的奖项。
我们现在来看看，图灵是如何创造图灵机这一概念，从而证明了，不存在一个算法能判断任何命题的真假。要证明任何一个数学问题，都必须首先了解问题中的每个词的定义是什么。因此图灵要证明不存在这样的算法，首要的问题是：什么是算法？算法的定义是什么？
事实上，在此之前，并没有人给「算法」这个词下一个明确的定义，人们对此只有一个简单的直觉。直观上，算法似乎描述了一个机械的计算过程，比如「先给这个数加 1，然后乘 2 」这句话是一个算法，因为它描述了一个机械的任务；而「先搞定这个客户，然后回来向我报告」这句话显然不是一个算法，因为它描述的任务并不机械。也就是说，算法必须最清晰地描述每一步的计算该怎么做，人只要理解了这个算法，就一定能机械地一步一步地完成它。这里的「机械」，指的是这个算法的每个步骤都不能再被分解为更简单的子步骤了，比如刚刚说的「先搞定这个客户」就不是机械的，原因在于这个任务还可以被分解成更简单的子任务，比如分解成「先找到这个客户的联系方式，然后找到他，最后搞定他」。所以，算法就是许多步骤的计算，每一步计算都用最清晰的语言来描述最基础简单的任务。
那么，一步最基础的计算包含了什么内容呢？举例来说，当我们拿出一张纸做最基础的数学计算，比如两个数的加减乘除时，这时我们接受的输入就是初始的两个数，需要的输出是另一个数，我们在纸上进行的最基本的操作，就是写下或擦去一些数字符号。进行计算时，我们的注意力并不是一直集中在某个符号上，而是会在不同的数字符号之间移动，也就是说每个时刻我们都在读取特定的符号。
其实这个例子已经展示了一步最基础的计算包含的所有内容了：给定一个符号串作为输入，一个一个符号地进行读取，读到某个符号时，根据规则进行一定的操作，这些操作包括擦掉这个符号、写下新的符号、读取下一个符号——这就是图灵所指出的计算的本质。这样一来，一套算法其实就是规定了，当读取到什么符号时，应该进行哪种操作。
图灵设想了一种机器来完成上述的计算过程：它从左到右依次读取一个符号串的每一个符号，这个机器还内置了一些规则，规定了读取到什么符号时要进行什么操作。这个机器就是大名鼎鼎的图灵机。
看起来这是一个很笨的机器，它能做的事很有限，跟如今的计算机根本没法比。然而图灵认为，图灵机已经把握住了所有计算的本质，任何计算都无法超出图灵机的范围，也就是说，不论多复杂的计算过程，只要它是机械的算法，那就一定能找到一个图灵机执行这个计算过程。图灵坚信这一点，当然他肯定无法从数学上完全证明这一点，因为「算法」并没有一个明确的定义，图灵所做的事其实正是在对算法下定义，他就把算法定义为图灵机能计算的，定义是没有办法被证明的，它只能被相信或者不相信。到了今天，「算法就是图灵机」这个信念，越来越被数学家和计算机科学家们接受，因为各种各样复杂的计算机器最终都被证明跟某个图灵机等价，现代计算机能做的事图灵机也能做，只是做的时间更长而已。
更严格地说，图灵的这个信念可以表述为「可计算的就是图灵机可计算的」，这个信念被称为「丘奇-图灵论题」。丘奇是图灵同时代的学者，他跟图灵几乎同时提出了自己对于算法的定义，图灵用图灵机来定义算法，而丘奇用了一种很不一样的方式来定义，因为丘奇对于计算本质的理解和图灵有差异，丘奇把他自己提出的定义叫做「 λ（读作兰布达）演算」。像图灵一样，他相信所有算法都能归结到自己提出的这个 λ 演算上。后来丘奇和图灵都意识到，图灵机和 λ 演算是等价的。熟悉编程的听众可能知道，命令式编程（比如C 语言）和函数式编程（比如 Haskell 语言）是很不一样的，其实从源头上来说，命令式编程和函数式编程对于「算法程序」的理解有本质的不同，这也导致它们对计算重点的把握不一样。这种不一样的来源就是图灵和丘奇对计算本质的理解不同。命令式编程起源于图灵对算法的理解，而函数式编程起源于丘奇的理解。
明确了算法就是图灵机之后，图灵证明了，不存在一个图灵机可以判断命题是否能从希尔伯特的符号系统中推出，这也就宣告了莱布尼茨之梦的破灭。而图灵机以及 λ 演算，就作为解决希尔伯特提出的问题的副产品，永远留在了这个世界上，计算机理论也随之发扬光大。
好了，这本书解读的差不多了。现在，我们回顾一下计算机科学的发展历程。
和牛顿同一时代的莱布尼茨提出了一个梦想，他希望把人类的一切知识符号化，然后找到一个算法来判断任何一个命题的真假。
百年之后，弗雷格被这一梦想打动并付诸行动。莱布尼茨希望把人类所有知识都符号化，但科学的爆发式发展显示，科学知识不太可能被符号化，不过严谨的数学还是有希望的。弗雷格认为数学的基础就是逻辑，基于他对数学和语言的哲学观点，他发明了许多符号，并且几乎成功地将一些数学符号化了。
尽管罗素悖论使弗雷格的工作失败了，但他创立的符号留了下来。
希尔伯特认为数学就是人工符号的游戏，基于这种思想，他用符号系统将绝大部分数学符号化，并且提出了三个重要的问题：符号系统能否推出所有真命题？符号系统能否证明自己无矛盾？是否存在莱布尼茨想要的那种算法？
哥德尔认为数学绝不是符号游戏，而一定是有意义、有真假的。基于这种信念，他证明了两个不完备定理，说明有些真命题无法被符号系统推出，符号系统也无法自证无矛盾性。
接下来，图灵和丘奇思考了人类计算的本质，从而给出了算法的定义，证明了不存在莱布尼茨想要的那种算法。
而最「有用」的计算机科学，就在这些天才们「无用」的哲学思想和纯数学研究中，作为一个副产物产生了。
读这本书，最重要的并不是获得有关计算机科学史的知识，而是感受到抽象思想的价值。当然，这不是在过分夸大思想的力量而贬低实践，我们都承认，冯·诺依曼对于现代计算机的贡献，并不在图灵之下。
我对这本书的推荐就到这里了。以上讲述的内容基于 2005 年 5 月湖南科学技术出版社出版的《逻辑的引擎》，希望我的推荐能让你对这本书的内容产生兴趣。
