还原计算-《逻辑的引擎》

很久以前写的一篇读书笔记，现在读来也觉得挺有意义，就分享到 steemit 上吧

前几天看了一个TED演讲，题目大概是“如何自己做一个烤面包机”。看完感触颇深，也许只有国外的人才有这样浪漫的想法。何处此言？想象一下自己穿越到了古代，没有任何现代化的工业设施，在这种情况下去做一个现在看来再简单不过的烤面包机。从最基本的元素铁，铜，硅，塑胶的获取和提炼到导线和绝缘体的构造，再到烤面包机的容器的成型，每一个小环节都将举步维艰。当然，演讲者最终做出来了一个“烤面包机，玩具”。好吧，结局似乎没那么完美，但对我来说有趣的部分并非是这个结果，而是作者的态度，勇敢的面对最简单最原始的问题，思考事物的本质。

仔细想来身边的一切并非都是那么理所当然，再想想这些句子：“1+1=2”；“在纸上写字”； “打开电灯”；“一辆汽车在马路上行驶”；“用谷歌搜索一下”；试试回答这些问题：加法和数字是怎么出现的？纸和文字又是怎么出现的？电灯和汽车呢？计算机呢？ 再一串连续的提问：这些东西因为什么而存在至今？是怎样的人以怎样的思维创造出来？如果愿意思考，个人觉得这些问题将魅力无穷。

再试着思考这个问题：“如何自己做一个计算机？”。想必无论谁被问到都只能是结舌，在我们理所当然认为的一切面前，计算机突然显得神秘强大，无从窥探。到底是怎样的头脑和智慧创造出计算机这样强大的存在？作为计算机专业的我同样对这个问题感到痴迷，想探寻计算机的本质，如何从无到有的过程。

从20世纪50年代以来，尽管计算机已经从一个庞然大物变成现在的ipone大小，其背后的本质依然没变，那就是逻辑。这也是为什么我要读《逻辑的引擎》，全书讲述了几个世纪以来数位天才科学家如何一步步发展出现在的计算机概念，而我也将在下面回顾这些伟人所做的贡献。

时间回到1646年，莱布尼茨于德国出生。莱布尼茨倾其一生奉献在数理逻辑中。正是因为他才萌芽了计算机逻辑概念的雏形：“符号体系，逻辑推理演算”。莱布尼茨发明了微积分符号体系，在莱布尼茨看来，我们对整个人类的知识领域也可以像操作微积分的符号一样，可以通过一些符号进行演算，推断出逻辑的真假。莱布尼茨将符号与概念联系在一起，通过符号来简化事物实体之间的复杂，这种符号是一种普遍的科学。对于现在的我们而言，很容易将莱布尼茨的符号与编程语言对应起来，也许这正是他毕生所最求的符号体系。

虽然莱布尼茨的梦想萌芽出了基本逻辑雏形，但却未做太多的实质性工作。而当我们讨论逻辑这个词的时候，第一想到的应该是bool，布尔值，当然这是为了纪念乔治.布尔，另一位天才。是他提出了这样的说法：“如果x表示白的东西，y表示绵羊，那么xy表示白的绵羊，如果z表示有角的，那么zxy应该表示有角的绵羊”。布尔意识到了传统逻辑句子里边的类以及类之间的关系并用符号来表示。并在《思维的法则》一书中做了体系化的推理。

布尔的逻辑代数就像一把利刃，通过布尔逻辑可以很容易证明下面的三段论：

条件：所有的x都是y；所有的y都是z；
结论：所有的x都是z。

证明：1. x=xy; 2. y=yz; 3. 带入1,2 得到 x=x(yz)=(xy)z; 4.将1带入3得到 x=xz


通过布尔逻辑可以解决很多其他逻辑推理问题，这是前所未有的，抽象的逻辑和盖帘被转化为代数符号之间的推理。但距离莱布尼茨的梦想仍然非常遥远。




而后弗雷格对逻辑运算做了更加细化的区分和探讨，也就是后来我们在代数里边看的这些符号“非，或，且，如果那么，任意，某个”，弗雷格的《概念文字》虽然体现了莱布尼茨梦想中的符号体系。可以处理各样的问题，但是莱布尼茨憧憬的更多的也许是一种能够有效的计算工具的语言。逻辑运算符号更适合做逻辑推理。尽管如此，弗雷格的理论已经可以使得用数学方法来研究数学活动本身成为可能。正是对这种可能的研究中得到了这样一则结论：不可能存在一种计算方法，能够说明某一推理过程是否正确。而图灵也正是在研究这一否定性结论的过程当中发现了了可以令莱布尼茨欣喜的东西，一种可以执行任何可能计算的通用机器，也就是计算机的概念原型。



一种新的事物和理论的产生总是因为当前的不足，并且带有偶然性。阿兰图灵为什么会想到通用机器，正如之前所说的，为了证明一个否定性结论，也许计算机的产生只是一个副产品。当然这并不重要，让我们回到这场争论的开端-康托尔的无限。




无限在康托尔的时代也许只能是神学和哲学才能探寻的领域，但无限却又是一个触手可及的事情，当我们数着1，2，3... 会发现，这将永无止境。无限让数学们感到沮丧，并不断的回避这一问题。然后康托尔却被无限的神秘所吸引，对无限做了系统性和前所未有的研究。我们很难想象自然数（1,2,3...）的数目和偶数(2,4,6...)的数目是相同的，当其时莱布尼茨和康托尔都意识到了对于每一个自然数都能找出一个唯一的偶数与其对应。莱布尼茨得出的结论是，自然数有数目这一概念是不一致的。 而康托尔得出的结论是某些无限集将与它的一个子集具有相同的元素数目（偶数是自然数的子集）。




从一开始，康托尔就面临着反对意见，一个生活在有限世界的人有限的人类竟然期望能够对无限做出有意义的断言，这使得大多数人不满，并且展开了激进的口舌之战。 这是这场争论的另外一个主角将登场-希尔伯特，一位伟大的哥延根数学家。 从莱布尼茨创立微积分（或者说莱布尼茨和牛顿）到希尔伯特成为数学家将近两个世纪的时间里，无限的思想已经开始被应用到诸多方面。 希尔伯特是康托尔的拥护者，他指出“在我看来，这是数学领域所考出的最令人惊叹的花朵”。1928年，希尔伯特和其学生出版了一本逻辑课本，书中提到了两个重要的问题，第一个：证明一阶逻辑的完备性。第二个问题：判定性问题，即对于一个一阶逻辑的公式，如何找到一种方法，可以在证明有限的步骤内判定这个公式是否是有效的。




莱布尼茨梦想把人的理性还原为计算，并通过机器执行这些计算。弗雷格第一次给出了一个能够解释人的一切演绎推理的规则系统。而后哥德尔证明了这个系统的完备性。哥德尔的工作让人们很难相信希尔伯特在判定性问题的算法存在。而这时，图灵则开始思考如何能够证明这样的算法是不存在的。

在图灵的研究过程中，将问题从研究规则转移到了人在执行他们时所做的实际工作。将本质还原为最基本的操作。只要证明仅仅执行那些基本操作的机器不可能判定“一个给定的结论是否可以用弗雷格的规则从给定的前提导出”，他就能够下定结论，判定问题的算法是不存在的。正是这种思考，图灵将计算过程同人的思考联系起来，人在做一个乘法的时候做了哪些最基本的步骤？ 图灵将人的思维过程划分成了最基本的单元，每次只能想到一个最基本的符号，拿12x13做比喻，人的思维过程应该是这样一串序列1,2,x,1,3,=。。。，图灵得出结论：

1. 在计算的每一个阶段，只有少数符号受到了注意。
2. 在每一个阶段所采取的行动仅仅取决于受到注意的哪些符号以及计算者当前的心灵状态。

图灵将这种分析与一条连续的纸带联系起来，并推论，任何计算都可以被看做是以如下的方式进行：

1. 计算通过一条被划分成方格的连续纸带上写下符号进行。
2. 计算者只注意当前方格的符号。
3. 下一步运算取决于这个符号和心灵状态，在当前方格写下一个符号，然后把注意力转向左边或者右边的一个方格
   
   
   
   
   很容易看出，这些“人类思考”的步骤完全可以通过机器去代替，这就是图灵机。 现在看来，这种思维方式正如我们用指针操作内存数据。就计算本身而言，图灵机是如何制造的并不重要，其本身更重要的是数学抽象。分析这种抽象，可以得出结论，通过某种算法程序可计算的任何东西都可以在一台图灵机上来计算。对于图灵的研究来说，这种思维更多的指的是图灵的“可计算数”。正如我们所看到的，图灵原本的目的是为了证明可判定性问题，但其新颖的证明思维产生出的却是计算机抽象的雏形，当然图灵和世界都意识到了图灵机的伟大， 引用图灵的一段话。

现在，让我们回到理论计算机的类比上来。可以证明，我们能够制造出一台特殊类型的机器来完成所有这一切工作。事实上，它可以作为任何其他机器的一个模型。这种特殊的机器或可被称为“通用机” - 阿兰.图灵 1947年

不得不说这是一段多么伟大和神圣的宣言，就像是图灵举着逻辑的旗帜在宣誓人类即将进入一个新的纪元。当然图灵所描绘的图灵机实现和现代计算机相比其复杂程度是远不能及。所有的这一切都将不可能是一个人的英雄主义式功劳，而必然是全人类的思维结晶。正如我所描述的阿兰图灵提出图灵机的历史，是经历了从莱布尼茨开始到图灵的几个世纪的故事。

对于科学的世界，我是还原论者，只有钻研到了最底层探索才能思考科学的本质，才能预见科学的发展。《逻辑的引擎》通过几则人物传记让我们可以窥见计算机理论模型的发展历史。作为读书笔记，也就到此。 书中有很多有趣的推理。如康托尔的无限的思考，哥德尔对于希尔伯特的一致性问题的推论。以及哥德尔其实是第一个程序员。着实有很多有趣的内容。

版权声明：自由转载-非商用-非衍生-保持署名（创意共享3.0许可证）