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

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

2、康托尔对角线方法康托尔对角线方法n1891年，康托尔使用对角线方法证明实数集是不可数的。n康托尔集合论：实无穷。n当时许多数学家只承认，有穷事物的发展过程是无穷尽的，无穷只是潜在的，是就发展说的。他们不承认已经完成的、已经存在着的无穷整体，例如集合论里的各种超穷集合。n潜无穷论者：高斯，克罗内克，彭加莱。罗素悖论罗素悖论直觉主义直觉主义n布劳维尔：荷兰数学家，提出了直觉主义思想，反对康托尔集合，认为罗素悖论是根源于非构造性的数学，强调构造性证明，反对基于无穷集的排中律。n构造性的数学，才是可靠的数学。n优点：可靠，计算科学先驱n缺点：杀伤力太强形式主义形式主义n为了捍卫古典数学的尊严，1904

3、年，希尔伯特在数学家大会上又提出一个证明算术无矛盾性的思路。n这个思路也称为形式主义纲领，它的核心思想是将算术表达为一种形式系统或称公理系统，然后用有穷步骤证明该系统的无矛盾性。语法：构造性语法：构造性语义：经典数学语义：经典数学哥德尔定理哥德尔定理n哥德尔研究了希尔伯特纲领，给出否定的答案，宣告希尔伯特纲领的失败。n1930年提出的哥德尔第二不完备性定理说，任何包含一阶算术的形式系统，该形式系统的无矛盾性，在该形式系统内无法通过有穷的步骤得到证明。n在定理的证明中，哥德尔还提出了很多有用的理论，比如如何把符号编码为自然数，还有使用递归函数来研究有穷证明的能力范围。语法：构造性语法：构造性语义

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

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

6、对角线方法和悖论：基于对角线引理和维特根斯坦思想对于悖论的分析，发表在中国分析哲学 2010n关于对角线方法：Wittgensteins analysis on Cantors diagonal argument，发表在2010年第七届国际认知科学大会。构造性的计算理论构造性的计算理论n关于对角线方法和计算理论：从形式主义的框框中摆脱出来，从构造性方面重新思考计算理论。对于原有的计算理论，保留其构造成分，消除其非构造成分。n奇怪之处：逻辑推理居然可以证明一个经验问题。过分夸大了逻辑的作用。矛盾的启发矛盾的启发n韩非子里有这样一个故事：楚人有鬻盾与矛者，誉之曰：“吾盾之坚，物莫能陷也。”又誉其矛

7、曰：“吾矛之利，于物无不陷也。”或曰：“以子之矛陷于之盾，何如？”其人弗能应也。n我们读完这个故事，并不会认为，这位楚人不能存在，或者更荒唐地认为，韩非子这本书并不存在。n我们只能说：书中这位楚人说的话里面有矛盾。因此，这位楚人应该修改他的话。逻辑的功能与局限逻辑的功能与局限n逻辑是已有知识的符号表达，在演绎封闭的意义上，逻辑并不能发现新知识。从信息的角度来看，演绎推理并不能增加信息量。这是由演绎推理的保真性决定的。n同样，逻辑矛盾并不能用来发现新知识。逻辑矛盾揭示的是已有概念间的矛盾，已有概念要进行修改或限制。nPS：先有人类知识，才有符号表达、逻辑表达和计算表达。在此意义上，机器智能不可能

8、超越人类智能。严格来说，如果人类有机器的速度，那么机器智能=人类智能。人类指一个方向，机器就往前冲。现有理论中的对角线方法现有理论中的对角线方法n在现有数学中，使用对角线方法证明了：实数集不可数。n在现有计算理论中，使用对角线方法证明了：停机问题不可计算。n在现有递归函数中，使用对角线方法证明了：一元递归函数不存在能行枚举。n小结：反证法，假设某前提，然后使用对角线方法得到矛盾。从而证明某结论。n分析：有一个隐藏的前提是函数处处有定义，然后才得出了矛盾。矛盾所揭示的，其实是该点的无定义性。计算理论需要更严格的基础计算理论需要更严格的基础n第二次数学危机：微积分刚出现的时候，基础并不稳固。dt有

9、时候被当成零有时候被当成非零。过了一百年左右，极限理论的出现，为微积分奠定了严格的基础。n第三次数学危机：计算科学出现了，基础也还有争议。有必要借鉴（潜无穷特征）极限理论，为计算理论提供严格的基础。一种构造性的计算理论一种构造性的计算理论n将构造主义进行到底n“要证明一个数学对象存在，必须指出这个对象是怎么构造出来的”n函数有不同的层次。每一层构造，有每一层构造的游戏规则。每一层构造，都在更新着“计算”的概念。n1、普通的递归函数：f(n)=n+1;n特点：输入任意n，就可以得到输出。n该函数已经完成已经确定。n2、通用函数：n特点：输入任意m和n，还需要先有还需要先有，才可以得到输出。n游戏

10、规则已经发生变化：通用函数依赖于一般函数的可数集。通用函数的完成与明确，有赖于一般函数的展开与明确。n函数作为参数。n2、通用函数：康托尔函数康托尔函数n3、特殊的通用函数康托尔函数：n特点：输入任意m，还需要先有还需要先有，才可以得到输出。n如果f是fi，现在问fi(i)=？这时候fi(i)=1-fi(i)。n这时候不是矛盾，而是没有定义。fi(i)的计算依赖于fi(i)自身，这是没有定义。n对于这个函数而言，至少在这一点上是没有定义的。n2、特殊的通用函数康托尔函数：存在一个康托尔函数与所有一元函数都不相同。所有已经展开的一元函数,都存在一个函数与之不同。“相互追随，趋于无穷相互追随，趋于

11、无穷”.不停机不可以吗？不停机不可以吗？n不停机有两种：一种是无意义的死循环，这种不停机意义不大。n但是，还有另外一种不停机。比如不断计算PI的更精确值的程序。比如通用图灵机计算机。n大脑，在某种意义上，也是一种图灵机。难道大脑也要停机才有结果吗？n所谓的停机，其实只是相对于那个计算需求而言。如果得到了需要的结果，这时候可以说这次计算停机了。n我们关注的是问题有没有得到解决，停机不停机又有什么关系呢？n一般函数与通用函数有不同的使用规则，当前计算理论却往往混为一谈。n应该分开一般函数与通用函数，来分析停机问题和递归定理。小结小结n将构造进行到底：计算科学独立出传统数学框架。n逻辑矛盾揭示的是已知概念间的矛盾。逻辑并不能用来发现新知识。对角线，哥德尔定理，停机问题证明中出现的矛盾，揭示的是思维中的某些混乱。n对于“所有”的构造性理解，对于函数的构造性理解，对于概念的构造性理解。n更无争议的计算理论基础：直觉主义与形式主义之间的第三种可能。n不可计算问题的再思考：停机问题等。