一种构造性的计算理论-知识论与认知科学研究中心-厦门大学

1、一种构造性的计算理论庄朝晖厦门大学计算机科学系通用计算计算通用通用计算：起源于莱布尼兹，将各种问题符号化数字化之后，进入计算过程。计算通用：万物之所以可以计算，是因为万物本来就是在计算。区别只是在于是不是使用数字进行计算。一切皆计算将构造进行到底计算科学的特点是：构造性，能行性和潜无穷。然而计算理论的研究框架却具有以下的特点：非构造性，非能行性和实无穷。例如数理逻辑的语义部分，例如计算理论的停机问题等等。提出的问题：有没有另一种可能性，使用构造性的框架来思考构造性的计算科学。回顾历史为了重新思考计算理论，有必要回顾计算科学历史。罗素悖论引起了第三次数学危机，在这次危机中走出了计算科学。康托尔对

2、角线方法1891年，康托尔使用对角线方法证明实数集是不可数的。康托尔集合论：实无穷。当时许多数学家只承认，有穷事物的发展过程是无穷尽的，无穷只是潜在的，是就发展说的。他们不承认已经完成的、已经存在着的无穷整体，例如集合论里的各种超穷集合。潜无穷论者：高斯，克罗内克，彭加莱。罗素悖论理发师悖论：在一个小镇上有一位理发师，这位理发师遵守这样的规则：“给而且只给那些不给自己理发的人理发”。现在问理发师是否要给自己理发。如果理发师不给自己理发，那么根据定义，他要给自己理发；如果理发师给自己理发，那么根据定义他不能给自己理发。直觉主义布劳维尔：荷兰数学家，提出了直觉主义思想，反对康托尔集合，认为罗素悖论

3、是根源于非构造性的数学，强调构造性证明，反对基于无穷集的排中律。构造性的数学，才是可靠的数学。优点：可靠，计算科学先驱缺点：杀伤力太强形式主义为了捍卫古典数学的尊严，1904年，希尔伯特在数学家大会上又提出一个证明算术无矛盾性的思路。这个思路也称为形式主义纲领，它的核心思想是将算术表达为一种形式系统或称公理系统，然后用有穷步骤证明该系统的无矛盾性。语法：构造性语义：经典数学哥德尔定理哥德尔研究了希尔伯特纲领，给出否定的答案，宣告希尔伯特纲领的失败。1930年提出的哥德尔第二不完备性定理说，任何包含一阶算术的形式系统，该形式系统的无矛盾性，在该形式系统内无法通过有穷的步骤得到证明。在定理的证明中

4、，哥德尔还提出了很多有用的理论，比如如何把符号编码为自然数，还有使用递归函数来研究有穷证明的能力范围。 语法：构造性语义：经典数学图灵哥德尔不完备定理出世后，在剑桥大学的图灵设想：能否有这样一台机器，通过某种一般的机械步骤，能够解决所有可以解决的数学问题。他提出了图灵机与图灵可计算。后来，他应邀到美国与丘奇教授一起工作，进一步研究了图灵不可计算的问题。形式主义成为主流至今，数学教科书都以康托尔对角线方法来证明实数集不可数。即使是以构造性为特征的计算科学，也被纳入康托尔集合论的框架中进行理解。奇怪：没有成功的纲领成为后来的主流？可能的原因：形式主义继承和发展了构造性，取得巨大的成果。语法：构造性

5、语义：经典数学被忽视的维特根斯坦维特根斯坦是罗素学生，上世纪最伟大思想家之一。他听了布劳威尔的讲座，大受震动，又开始思考。他深刻分析了对角线方法，哥德尔定理和各种悖论。他的相关思想长期被忽视。有人评论他是哲学家，而不是数学家，但是数学基础，在很大程度上，恰恰正是哲学问题。归结到对角线方法后来的研究表明，这些问题密切关联：康托尔对角线方法罗素悖论等诸多悖论哥德尔定理停机定理等不可计算问题一些研究工作关于对角线方法和哥德尔定理：基于直觉主义对哥德尔不完全性定理的评论从维特根斯坦的评论开始，发表在厦门大学学报（哲社版），并以此文获得“首届洪谦哲学论文奖”二等奖（一等奖空缺）。关于对角线方法和悖论：基

6、于对角线引理和维特根斯坦思想对于悖论的分析，发表在中国分析哲学 2010关于对角线方法：Wittgensteins analysis on Cantors diagonal argument，发表在2010年第七届国际认知科学大会。构造性的计算理论关于对角线方法和计算理论：从形式主义的框框中摆脱出来，从构造性方面重新思考计算理论。对于原有的计算理论，保留其构造成分，消除其非构造成分。理发师悖论理发师悖论：在一个小镇上有一位理发师，这位理发师遵守这样的规则：“给而且只给那些不给自己理发的人理发”。现在问理发师是否要给自己理发，这时候出现悖论。主流的（蒯因）解决方案：不存在这样的理发师。或者，不存

7、在能够遵守该规则的理发师。奇怪之处：逻辑推理居然可以证明一个经验问题。过分夸大了逻辑的作用。矛盾的启发韩非子里有这样一个故事：楚人有鬻盾与矛者，誉之曰：“吾盾之坚，物莫能陷也。”又誉其矛曰：“吾矛之利，于物无不陷也。”或曰：“以子之矛陷于之盾，何如？”其人弗能应也。我们读完这个故事，并不会认为，这位楚人不能存在，或者更荒唐地认为，韩非子这本书并不存在。我们只能说：书中这位楚人说的话里面有矛盾。因此，这位楚人应该修改他的话。逻辑的功能与局限逻辑是已有知识的符号表达，在演绎封闭的意义上，逻辑并不能发现新知识。从信息的角度来看，演绎推理并不能增加信息量。这是由演绎推理的保真性决定的。同样，逻辑矛盾并

8、不能用来发现新知识。逻辑矛盾揭示的是已有概念间的矛盾，已有概念要进行修改或限制。PS：先有人类知识，才有符号表达、逻辑表达和计算表达。在此意义上，机器智能不可能超越人类智能。严格来说，如果人类有机器的速度，那么机器智能=人类智能。人类指一个方向，机器就往前冲。对于理发师悖论的可能证明过程：假设有如此一位理发师。如果他要给自己理发，根据他的规则，他不给自己理发。如果他不给自己理发，根据他的规则，他要给自己理发。矛盾。因此假设不成立，如此一位理发师不存在。这样的证明过程是可疑的。以下我们进行新的分析。理发师的规则，对于他人都是没有问题的。问题发生在对于自己。以下是简化版。对于理发师悖论的分析例1：

9、理发师说：我给自己理发当且仅当我不给自己理发。 （在保留特征后的简化版）可能解决方案是：不存在能遵守该规则的理发师，不存在 既给自己理发又不给自己理发的理发师。这样的解决方案是有些奇怪的。本文的方案：规则对于“理发师要不要给自己理发” 没有定义，只是给出了一个矛盾式。如果认为存在定义，就会产生矛盾。两种方案比较：本来没有规则，谈不上有没有能守规则的人。本文的方案更根本。例2：理发师说：我给自己理发当且仅当我给自己理发。分析：规则对于“理发师要不要给自己理发”，什么都没有定义，只是给出一个重言式。共同的是，对于“理发师要不要给自己理发”什么都没有定义，什么都没有讲。没有给出定义的两种语句：矛盾式

10、是不懂得如何讲话，什么都没有讲。重言式是懂得如何讲话，但讲了一句废话，也什么都没有讲。递归函数的例子例3：f(x)=f(a) 当x=a分析：f(a)的值其实没有定义。例4：f(x)f(a)当x=a 分析：f(a)的值其实没有定义。如果认为存在定义，会产生矛盾。例5：f(x)=1-f(a) 当x=a，f(x)=0，其他情况分析：f(a)的值其实没有定义。如果认为存在定义，会产生矛盾。理发师貌似给出对于所有人的规则，然而其实上，他并没有给出对于自己的规则。对于自己，他只是给出了一个矛盾式，没有定义。数字化：罗素悖论的对角线形式设M为所有人的集合，则M是可数的，我们可以枚举M中的元素（ E1 ，E2

11、 ，）。 E1不给自身理发，则第一行第一列记为0。 E2适给自己理发，则第二行第二列记为1。例：E1：(0,0, 0,0,)E2：(1,1,1,1,)E3：(0,1,0,1,)E0表示理发师，理发师给且只给那些不给自己理发的人理发。因此，E0 = (1,0,1,)。 现在问：理发师要不要给自己理发？回答是：没有定义。递归函数形式所有一元递归函数 f1 ，f2 ， f1(1)=0，则第一行第一列记为0。f2(2)=1 ，则第二行第二列记为1。例：f1：(0,0, 0,0,)f2：(1,1,1,1,)f3：(0,1,0,1,)定义f(m)=1-fm(m)。如果f是fi，现在问fi(i)=？回答是没

12、有定义。现有理论中的对角线方法在现有数学中，使用对角线方法证明了：实数集不可数。在现有计算理论中，使用对角线方法证明了：停机问题不可计算。在现有递归函数中，使用对角线方法证明了：一元递归函数不存在能行枚举。小结：反证法，假设某前提，然后使用对角线方法得到矛盾。从而证明某结论。分析：有一个隐藏的前提是函数处处有定义，然后才得出了矛盾。矛盾所揭示的，其实是该点的无定义性。计算理论需要更严格的基础第二次数学危机：微积分刚出现的时候，基础并不稳固。dt有时候被当成零有时候被当成非零。过了一百年左右，极限理论的出现，为微积分奠定了严格的基础。第三次数学危机：计算科学出现了，基础也还有争议。有必要借鉴（潜

13、无穷特征）极限理论，为计算理论提供严格的基础。一种构造性的计算理论将构造主义进行到底“要证明一个数学对象存在，必须指出这个对象是怎么构造出来的”函数有不同的层次。每一层构造，有每一层构造的游戏规则。每一层构造，都在更新着“计算”的概念。1、普通的递归函数：f(n)=n+1;特点：输入任意n，就可以得到输出。该函数已经完成已经确定。2、通用函数：所有一元递归函数 f1 ，f2 ，定义f(m, n)=g( fm(n) )特点：输入任意m和n，还需要先有fm(n)，才可以得到输出。游戏规则已经发生变化：通用函数依赖于一般函数的可数集。通用函数的完成与明确，有赖于一般函数的展开与明确。函数作为参数。对

14、于“所有”的构造性理解2、通用函数：所有一元递归函数 f1 ，f2 ，定义f(m, n)=g( fm(n) )这里的“所有”，如何理解？实无穷理解：已经完成的。f已经明确。f（一元化后）甚至可能就在f1 ，f2 ，正是这点促成了对角线方法的使用。自引用：一方面，f依赖f1 ，f2 ，另一方面，f就在f1 ，f2 ，其中。所以，f依赖自己。潜无穷理解：不断展开的。f的意义必须伴随着 f1 ，f2 ，的展开而展开。康托尔函数3、特殊的通用函数康托尔函数：所有一元递归函数 f1 ，f2 ，定义f(m)=1- fm(m) 特点：输入任意m，还需要先有fm(m)，才可以得到输出。如果f是fi，现在问fi

15、(i)=？这时候fi(i)=1-fi(i)。这时候不是矛盾，而是没有定义。fi(i)的计算依赖于fi(i)自身，这是没有定义。对于这个函数而言，至少在这一点上是没有定义的。对于“所有”的构造性理解2、特殊的通用函数康托尔函数：所有一元递归函数 f1 ，f2 ，定义f(m)=1- fm(m) 这里的“所有”，如何理解？实无穷理解：f已经完成的，已经明确。存在一个康托尔函数与所有一元函数都不相同。潜无穷理解：不断展开的，f的意义必须伴随着 f1 ，f2 ，的展开而不断展开。所有已经展开的一元函数, 都存在一个函数与之不同。“相互追随，趋于无穷” f1(1) , f2(2), f3(3) f(1)f

16、(2)f(3).不停机不可以吗？不停机有两种：一种是无意义的死循环，这种不停机意义不大。但是，还有另外一种不停机。比如不断计算PI的更精确值的程序。比如通用图灵机计算机。大脑，在某种意义上，也是一种图灵机。难道大脑也要停机才有结果吗？所谓的停机，其实只是相对于那个计算需求而言。如果得到了需要的结果，这时候可以说这次计算停机了。我们关注的是问题有没有得到解决，停机不停机又有什么关系呢？一般函数与通用函数有不同的使用规则，当前计算理论却往往混为一谈。应该分开一般函数与通用函数，来分析停机问题和递归定理。小结将构造进行到底：计算科学独立出传统数学框架。逻辑矛盾揭示的是已知概念间的矛盾。逻辑并不能用来

17、发现新知识。对角线，哥德尔定理，停机问题证明中出现的矛盾，揭示的是思维中的某些混乱。对于“所有”的构造性理解，对于函数的构造性理解，对于概念的构造性理解。更无争议的计算理论基础：直觉主义与形式主义之间的第三种可能。不可计算问题的再思考：停机问题等。谢谢诸位老师！附录：对角线引理1962年，汤姆森（J.F. Thomson）发表论文“论几个悖论”，令人信服地显示所谓的语形悖论和语义悖论实际上有共同的结构，都与康托尔对角线方法有密切的关联。他基于康托尔对角线方法，提出对角线引理。汤姆森成功地将罗素悖论、格雷林悖论和理查德悖论等表达成对角线的形式。以下，我们来思考一下对角线方法。康托尔对角线方法18

18、91年，康托尔使用对角线方法证明：实数集是不可数的。以下是证明过程。设M为所有形如：(x1, x2, x3, x4) （其中的xi是0或1）的元素的集合。假设M可数的。那么我们可以枚举M中的元素。例如：E1=(0,0, 0,0,)E2=(1,1,1,1,)E3=(0,1,0,1,)在此基础上，定义E0 = (b1, b2, b3, bu,) ，其中b1与a1.1不同, b2与a2.2不同, 一般地, 对于所有的n，bn与an.n不同。在上例中，E0=(1,0,1,)。E0显然是M中的元素。现在，不妨设E0等于某一个Ei。然而，根据E0的定义，bi与ai.i不同，因此E0不等于Ei。矛盾。因此，

19、假设是错误的，集合M是不可数的。因为集合M与实数集之间可以建立一一映射，因此实数集也是不可数的。对于对角线方法的分析分析：在康托尔对角线证明中，bi的值除了0和1，还有一个可能是没有定义。一个隐含前提是，在该点有定义，从而导致矛盾的出现。所以，矛盾得到的结论应该是：在该点没有定义。维氏的正对角线方法设M为所有形如：(x1, x2, x3, x4) （其中的xi是0或1）的元素的集合。假设M可数的。那么我们可以枚举M中的元素。例如：E1=(0,0, 0,0,)E2=(1,1,1,1,)E3=(0,1,0,1,)在此基础上，定义E0 = (0,1,0,)。E0显然是M中的元素。现在，不妨设E0等于

20、某一个Ei。根据E0的定义，bi与ai.i相同，也就是说Ei的第i位定义为与自身相同。这时候，可以认为bi是没有定义的。因为这时候，这个规则说的是：“做与你所做的相同的事情！”，相当于什么都没有说。从以上的正对角线方法，很清楚地可以看出，Ei的第i位是没有定义的。这个性质不妨称为定义的“不完整性”。定义的不完整性正对角线方法与逆对角线方法是相似的，都具有定义的“不完整性”。维特根斯坦曾经问道：“为什么矛盾比同义语反复更加令人害怕？”维氏对于其他悖论的统一分析维特根斯坦虽然没有像汤姆森一样提出明确的“对角线引理”，但我们在他的著作中可以发现，他对于对角线相关悖论的分析方法也是一致的。在分析罗素悖论时，维氏说：“矛盾的根源在于把函项作为自身的函项。这种矛盾的结果意味着，f永不能作为一个论证用