逻辑的引擎

标题和《逻辑的引擎》同名，可想而知，应该就是一则读书笔记了。

三天时间，伴随着奥运会的进展逐步读完了此书，不得不表示某种程度上的惊叹。不仅仅是对作者娓娓道来的叙事风格表示惊叹（作者Matin Davis本身就是一个知名的数理逻辑学家），而且对电子计算机发展过程中所暗藏的逻辑的力量表示惊叹。刚才下去散步时头脑里将整本书串了一遍，这里就顺着刚才串联起来的一幕幕计算逻辑发展史做一个读书笔记似的记录吧。

-----------------------

莱布尼兹在他十岁那年受到了来自他家庭教师的关于亚里士多德逻辑系统的熏陶，并从此对寻求一种具有概念内涵的符号表极为热衷（从这里我们也不难理解 为何牛顿创建的微积分的符号体系远远落后于莱布尼兹）。莱布尼兹眼中的符号表应该具备这么一种能力——每个符号自身就代表了相应的概念（而并非如ABC等 等仅仅代表一个简单的标记），符号之间能够进行演算、从而能够推导出世间万物（包括数学、自然科学等等）。换句话说，莱布尼兹理想境界中的符号体系不仅能够展示人类当前的全部科学成果和理智的文化内涵，而且符号之间能够按照一定的规则不断演化、从而进一步扩充人类理智的知识领域！这是一个很诱人的设想，与莱布尼兹的乐天派性格密不可分，同时与当时落后的科技成果也有关。现在看来这个理念就显得不免有些幼稚而过于乐观了，但是"莱布尼兹的梦"最终还是激励了无数人，包括20世纪最为顶尖的数学家和逻辑学家哥德尔。

尽管莱布尼兹始终对这个设想如此的热衷，但由于受到英皇乔治一世家族谱事件的牵连，他并没有能够对这个设想展开多少实际的努力，而仅仅是依据亚里士多德简单的逻辑体系创建了一个很简陋的、很不完善的符号表，之后就去世了。

-----------------------

布尔的出现或多或少给本书增添了不少熟悉的氛围，毕竟"布尔代数"就连所有高中生都耳熟能详。布尔并不知道莱布尼兹关于符号逻辑体系的设想，而是在两百年后独立创建了布尔代数体系。但布尔依旧没有能够脱离代数的框架，而是在很大程度上模仿了初等代数的规则、从而建立了自己的体系。

关于布尔的叙述中最为有趣的一个部分是关于上帝存在性的证明。布尔给出了五个用自然语言描述的前提，然后使用自己创建的布尔代数体系将其翻译成为严谨的逻辑语句，最后通过符号演算得出结论——上帝是存在的。另外一个有趣的部分则是有关于布尔的小女儿，或许很多人都不知道《牛牤》的作者是谁（正是布尔的小女儿），更少的人知道《牛牤》背后隐藏着一个怎么样的凄惨而浪漫的爱情故事，所以这部分八卦内容读起来格外有趣（尽管只有短短一段话）。

-----------------------

如果说布尔针对莱布尼兹之梦给出了一个不太让人满意的饭前开胃品，那么弗雷格（19世纪最重要的逻辑学家之一）便给出了一顿丰盛的符号逻辑大餐！弗雷格一开始就确信逻辑应该是凌驾于那个时代的所有数学之上，换句话说，弗雷格一开始就决定创建出一个不依靠任何已知的代数学结论的符号逻辑体系（弗雷格心中一直将代数和几何严格的区分开来，尽管后来解析几何的发展模糊了几何同代数的沟壑），并依据这个符号逻辑体系推导出全部的代数学！

弗雷格基本上做到了这一点，不仅仅弥补了亚里士多德和布尔等人的逻辑体系的几项重要缺陷，而且第一次将逻辑学自身与其他数学领域区分开来、使逻辑学研究提高到了一个前所未有的高度。他早期开创性的《概念文字》一书也成为了逻辑学发展史上的经典之作。

然而就当弗雷格晚年想要出版他的符号逻辑体系的著作时，却收到了一封来自叫做罗素的年轻人的信，信中提到了一个在弗雷格体系下将会导致的悖论——那个著名的异常集合悖论（俗称"理发师悖论"）。这个悖论的出现就好比是一个晴空霹雳——既然结论出错了，那么整个体系所假定的前提必然有误。弗雷格受到这个打击之后几乎是一蹶不振。（话说哥德尔后来提出"不完备性定理"的过程和图灵关于希尔伯特"判定问题"不成立的研究似乎都有些此类形式的悖论的影子，感 觉很奇特。而且罗素提出这个悖论似乎还和哥德尔有些关系，记忆不是太清晰了 囧）

-----------------------

整本书中最为突兀的部分似乎就是康托尔的出现。康托尔关于超限数的研究对数学自身的发展起到了很大的作用，而且在希尔伯特的数学纲领中也占有一席之地，但在本书中似乎并不是那么重要。Davis真正想要借康托尔说明的，正是康托尔在进行超限数研究过程中引入的"对角线方法"（尽管这个方法并非康托尔的首创，但正如纳什将拓扑学中的"不动点原理"引入经济学研究所导致的拓扑学的名声大振一样，康托尔对"对角线方法"的使用同样如此）。这个方法很简洁，但是却是一种极为有效的构造具备新属性的集合的重要手段，后文很多地方都需要利用这种方法（哥德尔那篇终结了希尔伯特纲领的划时代的"形式逻辑系统中不可判定命题"论文就用到了对角线方法，书后面的注释有一长段简化的证明，很有趣；图灵关于"判定问题"不成立的证明也用到了对角线方法，而且还涉及到了图灵机和停机集合等重要的概念）。

康托尔尽管在数学发展史上绝对占有一席之地、家庭生活也很美满，然而，康托尔生前在学术界是备受排挤。克罗内克作为他的老师，最后却成了他的劲敌——由于克罗内克的威望和对康托尔超限数研究的不满，很多大学都不收留康托尔，这个情况间接导致了康托尔晚年显得比较凄惨和落寞（更加直接的原因来自于第一次世界大战对他内心造成的冲击和克罗内克持久的敌意）。而且也正是因为克罗内克的影响，整个德国和欧洲甚至全世界的数学发展都停滞不前，直到他去世为止，这也算是对这个著名数学家和逻辑学家的莫大讽刺了。

-----------------------

希尔伯特是一个幸运而天才的数学家和逻辑学家。他早期的成就来自于对"果尔丹猜想"的证明上，而果尔丹本人也因为对希尔伯特证明的反应而被世人牢记——"哇靠，这不是数学，这是神学！"（前两个字的感叹词是我加上去的 囧）。尽管希尔伯特那时已经具备了一流数学家的能力，然而由于克罗内克的存在（希尔伯特本人对于康托尔所做出的工作是极为赞赏和惊叹的），他早期的生活一直不好过。直到他30岁那年，克罗内克去世了，德国封闭古板的数学环境开始苏醒，希尔伯特本人的生活也逐渐好转、甚至还在同一年找到了一位一生的伴侣并在第二年生了个儿子。

希尔伯特在他事业的巅峰时期提出了23个有待解决的数学问题（这些数学问题中康托尔的超限数得到了明确的肯定，而且明确的将康托尔晚年想要解决的实数连续统问题作为23个问题之一提出），作为20世纪数学家们的挑战。这可以算作是希尔伯特一生中最为辉煌的时刻了，对这些问题的逐步解决也推动了数学和众多学科的发展。

就在希尔伯特的影响力将全世界范围内的数学家和数学学子们逐渐聚集到欧洲的同时，他最心爱的学生外尔却同另外一个叫做布劳威尔的年轻人站在了一起， 试图去建立一个同希尔伯特的数学纲领相左的直觉主义数学体系（具体过程这里就不多所说了，直觉主义是一种更加贴近哲学范畴的数学，因此也被纯粹理性的希尔波特斥为"步克罗内克刻板迂腐的后尘"）。但也正是由于直觉主义的影响，使希尔伯特提出了元数学（也叫"证明论"）的理念。元数学主张接受布劳威尔的批判，但是声称仅仅使用布劳威尔所能够接受的数学方法推导出整个希尔伯特数学纲领中的全部问题——即著名的"有限性方法推理"！也正是元数学的推行，为哥德尔那篇划时代的论文创造了契机。

-----------------------

提到这里，就不得不说到罗素和怀特海的工作——著名的《数学原理》，一个使用严格的规定和技巧、利用形式逻辑推导出整个数学体系的著作。希尔伯特元数学体系中基本的"有限方法"主要就是基于弗雷格的《概念文字》和这本《数学原理》，特别是《数学原理》一书中所建立的绝对严谨的PM体系，更是让希尔伯特信心十足。

但是，这里却存在一个问题——尽管PM体系的推理是严谨的，但是这个体系的前提是完备的么？换句话说，任何PM体系下的语句是否都可以在PM体系所规定的若干前提下进行推导、从而被证明是真命题或者是假命题？哥德尔这个才华横溢的年轻人对此发起了挑战。几乎没有多长时间，哥德尔就得到了希尔伯特想要的结论——PM体系是完备的。然而，哥德尔却使用了"非有限性方法"——一种被布劳威尔所不齿的、最终被希尔伯特抛弃的方法。正是在这样的情形下，哥德尔 开始思考如何在"有限性方法"、那屈指可数的若干严格的数学方法下一步步得到完备性的证明。

然而令哥德尔自己都感到意外的是，最终的研究却将他引入了一个相反的命题——如果非要使用有限性方法，那么系统的完备性将无法得到证明！换句话说，必然有一个命题，从系统的外部看来是真命题，然而在系统内部却无法得到证明。再换句话说，任何形式逻辑系统（严格来讲是基于自然数的形式逻辑系统，因为哥德尔的证明过程所利用到的编码技术和对角线方法就是基于此）都存在一个不可判定命题——不论是这个命题自身还是这个命题的否命题都无法在此形式逻辑系统内部得到证明。书中有关于简化的PA系统的不可判定命题的证明，主要是利用了自然数编码和对角线方法，叙述逻辑很清晰，非常值得一看。同样值得一提的是，哥德尔为了论文中叙述的方便，特意构造了一种特殊的"算法"，能够将自然语言中的推导转换成基本的自然数序列、以此来更加贴近元数学的理念，而这种"算法"几乎就可以被称作人类最早的"解释程序"、而哥德尔所采用的叙述风格也非常贴近现代函数编程的风格！（哥德尔后来还引入了一般递归的概念，是不是感觉很熟悉呢 囧）

哥德尔所做的工作几乎就等于是终结了希尔伯特的元数学梦想。那篇"论《数学原理》及其有关系统的形式不可判定命题"的论文也成了整个20世纪最为经典的论文之一。但是根据作者附注中的说法，元数学当前依然非常活跃，因为虽然哥德尔的论文所针对的形式逻辑系统是普遍的，人们却可以不断构建出更加完备而强壮的系统。哥德尔的理论介绍完毕后，书中关于哥德尔晚年思想（包括灵魂存在性和二元本质论的思想）和生活（妄想症和对医学与现代工程科技的极端不信任）的介绍简直让人动容。这种传记叙事和理论探究相结合的方式也使得本书格外的生动。

-----------------------

其实全书的前六章对形式逻辑的发展演绎的描述，都是为第七章图灵的出现做铺垫。第七章也成了全书名副其实的核心章节（尽管从字数上来看并不是如此 囧）。图灵机很多人都已经有所耳闻了，停机问题与停机集合也是如此。但是恐怕很少有人知道图灵机背后的故事。而此书，就提供了很好的一个供我们来了解图灵其人和他的理论的媒介。

图灵机的出现其实是由于图灵对希尔伯特"判定问题"的思考。"判定问题"是力求寻找一种算法，在这个算法下，任何命题都可以在简单的符号逻辑体系下通过有限的方法给推导出来；换句话说，这是一种万能的算法（也可以说是部分满足了"莱布尼兹之梦"的算法）！然而，哥德尔的不完备性定理对希尔伯特纲领造成的强烈冲击使得人们难以再去相信这么一种万能的灵丹妙药般的算法存在，外界的怀疑观点也占了上风。显然，图灵也是持有怀疑态度的，然而同其他激愤而排斥的怀疑论者不同的是，图灵试图利用数学的方法来从根本上严格证明——这个算法不可能存在！

正是基于这种背景，图灵机和停机集合的概念被创建。在此理论基础上，一个特殊的、不属于任何图灵机停机集合的集合被构建出来（构建方式依然是前面已经提到多次的"对角线方法"），而一种"寻求某个自然数是否包含于这个特殊集合之中"的算法则被证明是不存在的！如是，整个"判定问题"便被证明是不可解、不成立的。

然而，这并非咱们所关注的重点，抑或是说这并不是能够引起我们兴奋的最重要因素——最重要的部分是图灵为他所构建的图灵机规划的能力蓝图上！图灵一开始所关注的是某些特殊算法的图灵机实现（即在数学上论证——任何一种算法都可以被构建成一个图灵机），然而渐渐的，他就开始思考——是否存在那么一种通用的图灵机，只要将通用算法分解为更多的简单步骤，这台图灵机就能够处理所有的通用算法呢？最后他成功了，不仅说明了这是绝对可行的，而且还提出了程序和数据不加以分割的设计理念。这也为后来通用计算机的研制铺平了理论上的道路。

冯诺依曼的计算机结构其实便是基于图灵通用机的模型，而冯诺依曼这个虚荣心十足的数学天才只不过是利用了一些手段使得他的名字最终名闻遐迩，尽管当前对于他的实际贡献大小已经有了普遍的观点——他只不过是基于图灵的模型构建了EDVAC这台变种的通用图灵机而已。

-----------------------

最后两章几乎就没有涉及到技术层面上较为细致的讨论了，更多的是关于第二次世界大战期间世界范围内通用计算机研究的进展。包括第一台ENIAC（实际上，ENIAC仅仅是一台逻辑理念模糊的计算机器而已，然而由于18000根真空管同时工作的工程奇迹，这台计算机获得了无比崇高的名誉）、冯诺依曼参与的EDVAC（基于图灵通用机模型构造的一个变种）、图灵自己规划的ACE机器图纸（图灵的能力在第二次世界大战中完全体现了出来，包括密码破译机器的建造和ACE的规划等）、图灵通用机的物理忠实体现Pilot ACE等等。

最后一章涉及到了人工智能领域，主要是针对"机器是否能够拥有智能"的反对声音提出了异议——对塞尔的"机器的绝对无意识论"的怀疑，和对彭罗斯 （对霍金比较熟悉的人一定不会对彭罗斯这个名字感到陌生，也应该不会对《皇帝新脑》这本书感到陌生，这是一本彭罗斯在自己并非很擅长的非物理学领域的一本论著，但是观点很具有蛊惑力）引入哥德尔的不完备性定理来论证"机器智能不能存在"的否定（主要还是图灵一开始就指明了的观点——机器自身也会犯错，而歌 德尔的不完备定理是针对一个充斥着真理的形式体系）。

-----------------------

"我们必须知道，我们终将知道"。这是希尔伯特的墓志铭，也是在他得知哥德尔毁灭性的不完备性定理前、在一次数学大会上的演讲结束辞。我想，这句话用在此书末尾必定是合适的。而当我们看到莱布尼兹的头脑被用在了编辑家族谱、了解到康托尔由于克罗内克的排挤最终郁郁而终、知道哥德尔在纳粹德国占领地奥地利遭到激进学生的殴打而不得不决定迁居美国、发现图灵最后竟然是在一个自己为之做出了无数贡献然而却得不到承认的国家因为同性恋问题被发现而服毒自杀时，我们又能够明白些什么呢？

-- by jtuki