计算机起源的数学思想

数学算法俱乐部

日期：2020年09月19日

正文共：8999字12图

预计阅读时间：9分钟

来源：YK芽课

人类的历史可以看做一部关于解放的历史。也有这样的说法，懒惰是人类进步的动力。为了偷懒，人类不断的做着各种努力，发明了各种机器工具，将自己从繁重的劳动解放出来，另一方面，每一次大的进步，都需要解放思想，同时也带来了全人类思想的大解放。在这样的历程中，计算机的出现无疑将人类从很多繁重的作业中解放了出来。与此同时，有些人开始思考能否制造出可以像人类一样进行思考的机器，以将人类从创造性的劳动和逻辑思考中解放出来，交给机器去完成。

虽然计算机的出现，不到百年，然而为了它的出现，所进行的探索和研究，早已经历经数百年的历史。当然准确的说，这些探索和研究在当时实际并不是为了计算机产生而进行的，绝大多数只是做了一个无意的铺垫。或许我们并不熟悉这样的一个过程，老实说现代的大学教育中也很少提及计算机出现之前的那些历史。实际上，了解这样的一个过程，更有助于我们理解一个事物是如何产生出来，它背后的科学原理又是如何，让我们可以透过复杂的电路外表，接触到最本质的东西。可以让我们除了对科学家们的工作表示赞叹之外，也可以深入他们当初的思想过程，近距离地进行跨越时间和空间的沟通。这对于我们自己应该如何思考问题，创造性地提出自己的想法也是有所帮助的。

我们已经了解到这样的一些人物，乔治.布尔,康托，哥德尔，图灵，冯诺依曼。而我们的离散数学的教学中，本身太注重于知识本身的学习，而忽略了知识是如何被发现产生出来，以及不同的知识之间曾经的渊源和启发关系。而对于启迪思想来说，后者显然更为有力。

莱布尼茨之梦

早在17世纪的莱布尼茨就有一个伟大的构想，他希望可以将人类的思维像代数运算那样符号化，规则化，从而让笨的人通过掌握这样的规则变得聪明，更进一步的制造出可以进行思维运算的机器，将人类从思考中解放。从莱布尼茨为微积分所确定的依然在今天被沿用的符号中，我们可以看出他对符号具有良好的感觉，通过选择良好的符号，可以大大的简化运算的复杂性，甚至将这样的运算变成一种天然的过程。除了构想之外，莱布尼茨本身为了发展一种逻辑演算也进行了很多尝试，他得到的一些结果已经具有后来布尔的逻辑代数的雏形。

布尔的逻辑代数

19世纪的布尔，将逻辑代数化，发展出了逻辑代数成为后来计算机内部运算的逻辑基础。

在早期的研究中，布尔就已经认识到符号的力量，代数的力量正源于代表着量和运算的符号在几条基本规则的支配下体现出来的。后来，他开始思考能否将逻辑推理也像代数那样用符号和几条基本规则就可以完全表达。

他开始思考我们通常所说的某物具有某种性质，可以用一个类来表示，比如白的是x，绵羊是y，那么白绵羊就可以用xy来表示，这样日常生活中的概念开始具有代数的形式，用现代的术语来说上面的xy表示的正是交集。

他又继续思考，xx表示什么呢，他发现xx与我们普通的代数运算不同xx依然表示的是x。xx=x实际上成为布尔的逻辑代数的一个基本规则。

继续考虑下去，如果xx=x在普通的代数中意味着什么呢？xx=x，意味着x=1或者0.可以看到如果xx=x作为逻辑代数的基本规则，放在普通代数中意味着x=0或者1，那么逻辑代数是否意味着是01的普通代数呢。于是布尔得到一个基本原理，如果仅仅限于01，逻辑代数就变成了普通代数。关于这一点的思考，对于二进制运算的在逻辑代数中的主导作用具有很大的启发意义。

如果限于01，那么01在我们的逻辑代数中代表的意思又是什么呢。我们之前看到可以用x表示某个类，对应地那么0可以解释成没有任何东西属于它的类，1可以解释成包含所有对象的全体。同时布尔又开始考虑普通代数中的+-在逻辑代数中的意义，x+y可以表示具有x和y两种属性的对象集合，x-y表示具有x属性同时不具有y属性的对象集合。

考虑了这样的一些意义之后，接下来再看xx=x=> x-xx = 0 => x(1-x) = 0
现在我们以逻辑代数的观点看这个式子，它体现了这样一个含义：没有任何东西可以同时属于又不属于某个类。这点让布尔十分振奋，因为这刚好体现了亚里士多德的排中律，这就使他确信自己找对了路子。

继续下去，布尔发现三段论也可以用他的逻辑代数来表达。

所有x都是y x=xy(x中的任何东西也属于y，就等于说没有任何东西是属于x而不属于y的，也就是说x(1-y)=0)
所有y都是z y=yz

------------ ?
所有x都是z x=xz
x=xy
y=yz => x = xy = x(yz) = (xy)z = xz

最后，"如果x，那么y。"可以用x(1-y)=0来表示,可以这样理解这个式子意味着如果x=1，那么y=1。在这里一方面我们可以把"如果x，那么"理解为等同于前面的这样一句话"所有的x都是y",当然这两者有一个区别，现在的x，y表示的是命题，而原来的x，y表示的则是类概念。以今天的观点来看，前者是命题演算，后者是谓词演算。

但是如果从另一个方面，重新考虑这句话，比如x=1表示命题x为真，x=0表示命题x为假，xy=1表示x且y，只有x，y均为1，xy=1，如果x=0或y=0，xy=0，这点又与普通代数相一致。从这个方向思考下去，就可以看到今天的布尔代数的基本面貌了，上面的这个定义正是与运算。

布尔的逻辑体系，不仅包含了亚里士多德的逻辑体系，而且还超越了它，但是仍有无法表达的情形：所有失败的学生或者是糊涂的或者是懒惰的。

今天的布尔代数

回到今天，我们再看布尔再把逻辑转变成代数的过程中，所产生的逻辑代数在今天的计算机中扮演着什么样的作用。布尔代数只有1和0两个元素，not and or三种运算，用几张真值表就可以表达清楚。

AND | 1 0

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

1 | 1 0

0 | 0 0

这张表说明如果 AND 运算的两个元素有一个是 0，则运算结果总是 0。如果两个元素都是 1，运算结果是 1。例如，“太阳从西边升起”这个判断是假的(0),“水可以流动”这个判断是真的（1），那么，“太阳从西边升起并且水可以流动”就是假的（0）。

OR | 1 0

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

1 | 1 1

0 | 1 0

这张表说明如果OR运算的两个元素有一个是 1，则运算结果总是 1。如果两个元素都是 0，运算结果是 0。比如说，“张三是比赛第一名”这个结论是假的（0），“李四是比赛第一名”是真的（1），那么“张三或者李四是第一名”就是真的（1）。

NOT |

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

1 | 0

0 | 1

这张表说明 NOT 运算把 1 变成 0，把 0 变成 1。比如，如果“象牙是白的”是真的（1），那么“象牙不是白的”必定是假的（0）。

如此简单的运算，实际上当时的布尔也不会想到它会被运用到计算机中，直到1938 年香农在他的硕士论文中指出用布尔代数来实现开关电路，使得布尔代数成为数字电路的基础。所有的数学和逻辑运算，加、减、乘、除、乘方、开方等等，全部能转换成二值的布尔运算。

用计算的力量改变世界是每一个程序员的梦想，YaK团队抱着对教育的敬仰和热忱，开发了有趣的YaK编程工具以及配套的系统化教学课程。让孩子可以用编程去学习和理解上帝的语言：数学。

前言：人类的历史可以看做一部关于解放的历史。也有这样的说法，懒惰是人类进步的动力。为了偷懒，人类不断的做着各种努力，发明了各种机器工具，将自己从繁重的劳动解放出来，另一方面，每一次大的进步，都需要解放思想，同时也带来了全人类思想的大解放。在这样的历程中，计算机的出现无疑将人类从很多繁重的作业中解放了出来。与此同时，有些人开始思考能否制造出可以像人类一样进行思考的机器，以将人类从创造性的劳动和逻辑思考中解放出来，交给机器去完成。

前面我们看到计算起源的数学思想有莱布尼茨，布尔代数。接下来我们看到其他的数学思想在计算中的运用。

弗雷格的突破与绝望

弗雷格的一生主要发表了这样三本著作：《概念演算--一种模仿算术语言构造的纯思维的符号语言》（1879）、《算术的基础--对数概念的逻辑数学研究》（1884）《算术的基本规律》（l卷 1893，2卷1903）。

其中概念演算，将普通数学中的一切演绎推理都包含在内，成为第一个完备的逻辑体系。布尔以普通代数为基础，用代数符号来表示逻辑关系。与此相反，弗雷格想以他的逻辑为基础而把代数构造出来。实际上这成为日后一个重要的学派"逻辑主义",在他们看来逻辑与数学的关系就像一门学科的基本部分和高等部分之间的关系。

弗雷格的逻辑体系，表现在今天就是我们数理逻辑中的命题演算和谓词演算(用数学的方法研究关于推理、证明等问题的学科就叫做数理逻辑。也叫做符号逻辑)。弗雷格第一次用精确的句法构造出形式化的人工语言，使得逻辑推理表示为机械演算即所谓的推理规则成为可能。从这个观点看，概念文字是我们今天使用的计算机程序设计语言的前身。

弗雷格希望可以自然数提出一种纯粹逻辑的理论，从而证明算术，微积分乃至一切数学都可以看成逻辑的一个分支。于是弗雷格便希望可以用纯逻辑的术语来定义自然数，然后再用他的逻辑导出它们的性质。例如3这个数将被解释为逻辑的一部分。弗雷格的思想是把3定义为所有元素数为3的集合的集合。实际上这就是《算术的基础--对数概念的逻辑数学研究》这部著作的主要内容。

然而正是这样的一些工作，1902年，年轻的伯特兰.罗素据此提出那个著名的罗素悖论。弗雷格的算术使用了集合的集合这样一种概念。罗素指出，用集合的集合进行推理很容易导致矛盾。罗素的悖论可以这样描述：如果一个集合是它自身的一个成员，那么就把集合成为异常的，否则它就是正常的。那么由所有正常集合组成的集合是正常还是异常的呢？

如果是正常的，那么它应该包含自身，这样它就应该是异常的。如果是异常的，那么它就不会包含自身，这样它就应该是正常的。无论哪个结果都导致了矛盾。实际上罗素构造这个悖论的方法，与之后哥德尔，图灵构造不可判定命题却有着神似的地方。然而这一矛盾却表明弗雷格构造的算术体系所基于的那些前提是靠不住的，并给弗雷格带来了巨大的打击。

虽然弗雷格的逻辑已经很完备，但仍然具有一些局限性。他的规则并没有提供判定某个结论能否从给定的前提中推导出来的计算步骤。另外能否找到一种计算方法，它能够说明在弗雷格的逻辑中某一推理是正确的呢？其结果是这样一则证明：没有这样的一般方法存在。然而正是在证明这样一条否定性的结论过程中，阿兰图灵发现原则上可以设计出一种通用机，它可以执行任何可能的计算。

弗雷格的研究开启语言哲学的大门，后来人们在寻找证明逻辑推理正确性的过程中，图灵发现了通用机，也就是今天计算机的数学模型。

康托尔，对无限的探索

康托尔进入无限的世界，开始无限的数目的研究。他发现自然数与实数具有不同的基数，以及由此提出的连续统假设，即实数和自然数之间不存在具有其他基数的集合。这也是1900年，希尔伯特提出的23个问题中的第一问题。这个问题直到今天并未完全解决，1938年哥德尔和1963年保罗科恩的重大发现表明，如果连续统假设问题可以被解决，就必须超越普通数学的方法。

对于我们普通人来说，最有用的大概是康托尔在证明实数与自然数基数不同的过程中所采用的对角线方法，这种方法是1891年，康托尔在一篇4页的论文中发表的。而对角线方法，在以后的故事中仍然会被用到，它将会被哥德尔用来解决一致性问题时构造系统内不可证命题，然后阿兰.图灵又再次使用了哥德尔的方法构造出了不可判定命题。而关于连续统假设的研究也引发了关于图灵机的构想。现在我们可以看到康托尔的工作与计算机的起源在这里产生了联系。

关于对角线方法，我们从自然数集来看，我们可以发现自然数与自然数的子集组成的集合之间具有不同的基数，假设我们把自然数与不同的自然数子集建立一个对应关系，1: M1 2: M2....，采用对角线方法，我们总是可以构造出一个新的自然数集，它没有任何自然数与之对应，我们这样产生这个新的自然数集：如果i属于Mi,那么排除i，否则包含i，容易看到这样产生的一个集合不同于任何的Mi。可见由一切自然数集组成的集合的基数要大于自然数的基数。

实际上康托尔并不是第一个关注到无限的数目特殊性的人，早在17世纪，莱布尼茨就发现偶数和自然数是一一对应的，正如他所说：对于任何一个数，都存在一个与之对应的偶数，那就是它的二倍。因此所有数的数目并不比偶数的数目更多，也就是说整体没有部分大。但是他得出了这样一个结论：所有自然数的数目这一概念是不一致的，讨论一个无限集中元素的数目是没有意义的。但是康托了选择了另一条路，他承认某些无限集将与它的一个子集具有相同的元素数目。正是基于这样一个大胆的选择，他才创立了关于无限的新理论。

当康托尔提出这些观点之后，立刻引来了各方面的责难。与弗雷格类似，人们发现用康托尔的超限数进行不加限制的推理会导致荒谬的结果。比如如果存在一个由所有基数组成的集合，那么它的基数该是多少呢？它必须比所有基数都大，但一个基数又怎么可能比所有基数都大呢？后来罗素又指出这样的一个问题：是否存在一个所有集合的集合？如果存在，那么倘若把对角线方法应用于它，会出现什么结果？这样我们会得到一个不同于所有那些已经拥有标签的集合的集合。正是在考虑这种情况时，罗素发现他那个关于由一切不是自身的集合组成的集合的著名悖论，也就是他向弗雷格传达的那个悖论。这里我们看到，弗雷格和康托尔之间被罗素悖论联系起来。而关于这个悖论的讨论和思考，则引发了数学史上的第三次危机。

大卫希尔伯特

希尔伯特是20世纪的数学领袖，1900年他在数学家大会上指出的23个问题，其中第二个便是关于算术一致性的问题。即關於一個公理系統相容性的問題，也就是判定一個公理系統內的所命題是彼此相容無矛盾的，希爾伯特希望能以嚴謹的方式來證明任意公理系統內命題的相容性。

希尔伯特纲领所提出的主要问题就是算术一致性问题。为了解决这个问题，希尔伯特发展出了元数学，一致性证明将在元数学内部完成。1928年，希尔伯特和他的学生阿克曼出版了一本逻辑课本，书中提出了关于弗雷格<<概念文字>>的基本逻辑(后来被称为一阶逻辑)两个主要问题，一个就是，证明一阶逻辑的完备性，即任何一个从外部看来有效的公式都可以只用课本里提出规则从系统内部导出。第二个问题以希尔伯特的判定问题而闻名，即对于一个一阶逻辑的公式，如果找到一种方法，可以在定义明确有限步骤内判定这个公式是有效的。这两个问题分别为哥德尔和图灵解决，而在解决第二个问题的过程中，图灵提出了图灵机的概念。

后来在1928年的国际数学家大会上，希尔伯特又提出一个关于形式系统的问题，这个系统建立在把一阶逻辑应用于现在被称为皮亚诺算术或者PA的自然数公理系统的基础之上。希尔伯特希望可以证明PA是完备的，也就是说任何一个可以在PA中表出的命题或者可以在PA中被证明为真，或者可以被证明为假。两年后，这个问题被一个叫哥德尔的年轻人解决了，但答案却完全不像希尔伯特料想的那样。

哥德尔完备性定理

希尔伯特在20世纪20年代介绍了他的元数学纲领：一致性有待证明的公理将被包含在一个形式逻辑系统之内，而证明仅仅是有限数目的符号的一种排列而已。当希尔伯特开始思考希尔伯特纲领时，希尔伯特的学生阿克曼和冯诺依曼似乎正在朝着用有限性方法证明PA的一致性的方向大步迈进。他们二人都已经为PA的一个有限的子系统找到了这样的证明，成功似乎指日可待。

这样哥德尔开始试图将算术一致性还原为PA的一致性，然而就是在这样的努力中失败了。哥德尔开始思考这些问题时，他重新思考了从外部而不是从内部考察一个系统的意思。从外部看，这些系统包含着符号串之间的关系。从内部看，这些系统能够表达关于不同数学对象的命题。哥德尔通过给符号串用自然数编码，将外部带到了内部。

哥德尔发现存在这样的命题，它们从系统外部看是真命题，但无法在系统内部得到证明。于是他得出了一个非凡结论：一种有意义的数学真理的观念不仅是存在的，而且其范围还超出了任何给定的形式系统的证明能力。在1931年，他发表的论文<<论 <数学原理>及有关系统的形式不可判定命题>>中，他选择对形式系统PM给出了他的结果，从而说明即使强逻辑系统也不可能把全部数学真理包含在内。

在哥德尔的证明中，关键的一步在于他证明了：一个自然数作为PM中可证命题的一个代码，这一性质本身可以在PM中表示出来。根据这一事实，哥德尔可以在PM中构造出一些命题，这些命题可以被看做表达了这样一个断言，即某些命题在PM中是不可证的。也就是说他可以构造出一个命题A，该命题经译码后可以断言某一命题B在PM中是不可证的。现在，在没有获知密码的人看来，命题A不过是一串符号而已，但是通过代码，神秘性就消失了：A表示这样一个命题，即某个符号串B表示在PM中一个不可证的命题。A和B通常是不同的命题，哥德尔问，它们是否有可能是相同的呢？事实上它们可以是相同的，哥德尔可以利用对角线方法证明这个结论。

运用这些技巧，我们可以使被断言为不可证的命题和做出这一断言的命题是同一个命题。换句话说哥德尔发现了如果获得这样一个非凡的命题，我们将它称之外U，具有如下性质：

U说某个特殊命题在PM中不可证。
那个特殊的命题就是U本身。
因此，U说"U在PM中不可证"

如果我们承认PM中证明的任何命题都是真的，那么我们发现U是真的，但它在PM中不可证。

U是真的。假定它是假的，那么它表述的内容就是假的，因此它就是不是不可证的，而一定是可证的，从而是真的，这与开始假定U是假的矛盾，所以它一定是真的。因为它是真的，所以它表述的内容为真，所以它在PM中不可证。

我们把U称为不可判定命题，当然这种不可判断性只与系统内部的可证性，从我们外部的观点来看U是真的。

另一方面，在PM内部，我们可以证明：如果PM是一致的，那么U。因此正是PM是一致的这一个假定，才使U在PM内部得不到证明。既然我们知道U在PM内部是不可证的，我们就必须得出结论说，PM的一致性在PM中不可证。而希尔伯特的主要目的就在于：用于被认为构成PM的一个非常有限的子集的有限性方法来证明像PM这样的系统的一致性。然而哥德尔证明了，即使就PM的全部能力而言，它也不足以证明自身的一致性。于是希尔伯特纲领走到了尽头。

图灵和图灵机

在哥德尓1930年的博士论文中证明了弗雷格的规则是完备的，这样就回答了希尔伯特1928年提出的第一个问题。而第二个问题即判定问题，在哥德尔的工作发表之后，人们很难想象存在这样的判定算法，于是阿兰图灵开始思考如果证明这样的算法是不存在的。

图灵采取了这样的一条道路，他首先分析了人的计算过程。通过丢掉非本质的细节，将这些计算活动局限在少数几种极为简单的基本操作上。然后图灵说明人可以被一个能够执行这些基本操作的机器所替代。然后只要证明仅仅执行那些基本操作的机器不可能判定一个给定的结论是否可以用弗雷格的规则从给定的前提中导出，这样他就能够下结论说，判定问题的算法是不存在的。

作为副产品，他对计算过程的分析，产生了通用计算机的一个数学模型。

他观察到：在计算的每一个阶段，只有少数符号受到了注意。每一个阶段所采取的行动仅仅取决于受到注意的那些符号以及当前的心灵状态。

然后他做出了如下抽象：计算通过在一条被划分成方格的纸带上写下符号来进行。执行计算的人在每一步都只注意其中一个方格的符号。她的下一步将仅仅取决于这个符号和她的心灵状态。她的下一步是这样的：她在当前注意的方格里写下一个符号，然后将注意力转向它左边或者右边的相邻符号。

现在可以很容易看出，做这项工作的人可以用一个机器替代，纸带在机器上来回移动。关键之处在于图灵对于计算概念的分析，通过某种算法程序可计算的任何东西都可以通过一台图灵机来计算。因此如果我们可以证明某些任务无法用图灵机完成，那么我们就可以说没有任何算法可以完成这项任务。这就是图灵证明判定问题不存在算法的方法。

实际上一台图灵机可以用这样的一个五元组来表示：当机器处于状态R，注视纸带上的符号a时，它将用b来代替a，向右移动一个方格，然后转到状态S。而一个具体的算法便可以由这些五元组表示的状态转换的集合组成的图灵机来表示出来。R a:b -> S 或者R a:b <- S

图灵将对角线方法应用于这种情况，得到了图灵机不能解决的问题，由此推出了判定问题的不可解性。与哥德尓类似，图灵采用了对角线方法也对图灵机通过自然数进行了编码。

图灵机本身可以是自然数编码表示，这样它也作为自身的输入。实际上有些输入会使图灵机停止下来，另一些则不会。这样一台图灵机就具有一些停机集合。如果我们考虑把一台图灵机的停机集合组成了一个包裹，并且认为那台机器的码数就是这个包裹的标签。对角线方法允许我们构造出一个与图灵机的任何停机集合都不同的自然数集合，我们称之为D。方法是这样的，我们考虑把图灵机的编码作为自身的输入，如果它的编码数不属于自身的停机集合，那么我们就把它加入D。而集合D则不是任何图灵机的停机集合。

然后考虑这样一个问题：
找到一种算法，判定一个给定的自然数是否属于集合D。

这就是一个不可解问题的例子。首先如果存在这样的一个算法，我们就能找到这样的一个图灵机，但是我可以改造一下这个图灵机，把以下两个五元组加入到这个图灵机：F 0:口-> F 和 F 口:口-> F。对于这个新的改进的图灵机来说，如果输入的数属于D那么那么机器就会像以前一样运转，并输出1而告终，如果输入的数不属于D，那这台机器将永远向右移动。这样我们就找到了一台图灵机它的停机集合刚好就是D。于是与我们的对角线方法矛盾。所以并不存在这样的一个算法。由此可知判断问题在算法上是不可解的。

为了验证自己工作的有效性，图灵又提出了通用机模型，通用机包含了图灵机代码以及待处理的数据。而这刚好对应着我们今天的机器，程序与数据的概念。也为存储程序计算机提供了一个模型。正是图灵在证明判定问题的不可解性是，对计算概念的分析以及对通用机的发现促使了计算机的产生。

1945年图灵又发表了他那篇著名的ACE(自动计算机)报告。这是对计算机的一次完整的描述，一直到逻辑电路图。也就是在这时冯诺依曼提出了他著名的"关于EDVAC的报告草案"，它实际上主张将要建造的EDVAC作为图灵通用机的一个物理模型实现出来。在这个报告里，提出了存储程序的概念，也就是沿用至今的冯诺依曼结构，实际上它的革命性不在于存储程序而是通用性，存储程序只是达到这一目的的一种手段。

1950年，图灵又发表了他的经典论文，计算机与智能，提出了著名的图灵测试来测试计算机是否具有智能。1954年6月7日，图灵咬了一个浸过氰化物的苹果，结束了自己的生命。而他的通用机思想却延续到今天。

— THE END —

☞0.00...1是个什么数？

☞图论的各种基本算法

☞82岁江泽民在2008年发表论文指出：发展智能化，机器学习将有所作为……

☞机器学习中需要了解的 5 种采样方法

☞北大读博手记：怎样完成自己的博士生涯？非常具有指导性！

☞从七桥问题开始：全面介绍图论及其应用