一种构造性的计算理论通用计算——计算通用通用计算：起源于莱布尼.doc

一种构造性的计算理论通用计算——计算通用通用计算：起源于莱布尼一种构造性的计算理论通用计算——计算通用 通用计算：起源于莱布尼兹，将各种问题符号化数字化之后，进入计算过程 计算通用：万物之所以可以计算，是因为万物本来就是在计算区别只是在于是不是使用数字进行计算 一切皆计算……将构造进行到底 计算科学的特点是：构造性，能行性和潜无穷 然而计算理论的研究框架却具有以下的特点：非构造性，非能行性和实无穷例如数理逻辑的语义部分，例如计算理论的停机问题等等 提出的问题：有没有另一种可能性，使用构造性的框架来思考构造性的计算科学回顾历史 为了重新思考计算理论，有必要回顾计算科学历史 罗素悖论引起了第三次数学危机，在这次危机中走出了计算科学 康托尔对角线方法 1891年，康托尔使用对角线方法证明实数集是不可数的 康托尔集合论：实无穷 当时许多数学家只承认，有穷事物的发展过程是无穷尽的，无穷只是潜在的，是就发展说的他们不承认已经完成的、已经存在着的无穷整体，例如集合论里的各种超穷集合 潜无穷论者：高斯，克罗内克，彭加莱罗素悖论 理发师悖论：在一个小镇上有一位理发师，这位理发师遵守这样的规则：“给而且只给那些不给自己理发的人理发”。

现在问理发师是否要给自己理发 如果理发师不给自己理发，那么根据定义，他要给自己理发；如果理发师给自己理发，那么根据定义他不能给自己理发直觉主义 布劳维尔：荷兰数学家，提出了直觉主义思想，反对康托尔集合，认为罗素悖论是根源于非构造性的数学，强调构造性证明，反对基于无穷集的排中律 构造性的数学，才是可靠的数学 优点：可靠，计算科学先驱 缺点：杀伤力太强 形式主义 为了捍卫古典数学的尊严，1904年，希尔伯特在数学家大会上又提出一个证明算术无矛盾性的思路 这个思路也称为形式主义纲领，它的核心思想是将算术表达为一种形式系统或称公理系统，然后用有穷步骤证明该系统的无矛盾性哥德尔定理 哥德尔研究了希尔伯特纲领，给出否定的答案，宣告希尔伯特纲领的失败 1930年提出的哥德尔第二不完备性定理说，任何包含一阶算术的形式系统，该形式系统的无矛盾性，在该形式系统内无法通过有穷的步骤得到证明 在定理的证明中，哥德尔还提出了很多有用的理论，比如如何把符号编码为自然数，还有使用递归函数来研究有穷证明的能力范围 图灵 哥德尔不完备定理出世后，在剑桥大学的图灵设想：能否有这样一台机器，通过某种一般的机械步骤，能够解决所有可以解决的数学问题。

他提出了图灵机与图灵可计算后来，他应邀到美国与丘奇教授一起工作，进一步研究了图灵不可计算的问题形式主义成为主流 至今，数学教科书都以康托尔对角线方法来证明实数集不可数 即使是以构造性为特征的计算科学，也被纳入康托尔集合论的框架中进行理解 奇怪：没有成功的纲领成为后来的主流？ 可能的原因：形式主义继承和发展了构造性，取得巨大的成果被忽视的维特根斯坦 维特根斯坦是罗素学生，上世纪最伟大思想家之一 他听了布劳威尔的讲座，大受震动，又开始思考 他深刻分析了对角线方法，哥德尔定理和各种悖论 他的相关思想长期被忽视有人评论他是哲学家，而不是数学家，但是数学基础，在很大程度上，恰恰正是哲学问题归结到对角线方法 后来的研究表明，这些问题密切关联： 康托尔对角线方法 罗素悖论等诸多悖论 哥德尔定理 停机定理等不可计算问题一些研究工作 关于对角线方法和哥德尔定理：《基于直觉主义对哥德尔不完全性定理的评论――从维特根斯坦的评论开始》，发表在《厦门大学学报（哲社版）》，并以此文获得“首届洪谦哲学论文奖”二等奖（一等奖空缺） 关于对角线方法和悖论：《基于对角线引理和维特根斯坦思想对于悖论的分析》，发表在《中国分析哲学 2010》 关于对角线方法：《Wittgenstein's analysis on Cantor's diagonal argument》，发表在第七届国际认知科学大会。

构造性的计算理论 关于对角线方法和计算理论：从形式主义的框框中摆脱出来，从构造性方面重新思考计算理论对于原有的计算理论，保留其构造成分，消除其非构造成分理发师悖论 理发师悖论：在一个小镇上有一位理发师，这位理发师遵守这样的规则：“给而且只给那些不给自己理发的人理发”现在问理发师是否要给自己理发，这时候出现悖论 主流的（蒯因）解决方案：不存在这样的理发师或者，不存在能够遵守该规则的理发师 奇怪之处：逻辑推理居然可以证明一个经验问题过分夸大了逻辑的作用矛盾的启发 《韩非子》里有这样一个故事：楚人有鬻盾与矛者，誉之曰：“吾盾之坚，物莫能陷也又誉其矛曰：“吾矛之利，于物无不陷也或曰：“以子之矛陷于之盾，何如？”其人弗能应也 我们读完这个故事，并不会认为，这位楚人不能存在，或者更荒唐地认为，《韩非子》这本书并不存在 我们只能说：书中这位楚人说的话里面有矛盾因此，这位楚人应该修改他的话 逻辑的功能与局限 逻辑是已有知识的符号表达，在演绎封闭的意义上，逻辑并不能发现新知识从信息的角度来看，演绎推理并不能增加信息量这是由演绎推理的保真性决定的 同样，逻辑矛盾并不能用来发现新知识逻辑矛盾揭示的是已有概念间的矛盾，已有概念要进行修改或限制。

PS：先有人类知识，才有符号表达、逻辑表达和计算表达在此意义上，机器智能不可能超越人类智能严格来说，如果人类有机器的速度，那么机器智能<=人类智能人类指一个方向，机器就往前冲 对于理发师悖论的可能证明过程：假设有如此一位理发师如果他要给自己理发，根据他的规则，他不给自己理发如果他不给自己理发，根据他的规则，他要给自己理发因此假设不成立，如此一位理发师不存在 这样的证明过程是可疑的以下我们进行新的分析 理发师的规则，对于他人都是没有问题的问题发生在对于自己以下是简化版对于理发师悖论的分析 例1：理发师说：我给自己理发当且仅当我不给自己理发 （在保留特征后的简化版） 可能解决方案是：不存在能遵守该规则的理发师，不存在 既给自己理发又不给自己理发的理发师这样的解决方案是有些奇怪的 本文的方案：规则对于“理发师要不要给自己理发” 没有定义，只是给出了一个矛盾式如果认为存在定义，就会产生矛盾 两种方案比较：本来没有规则，谈不上有没有能守规则的人本文的方案更根本 例2：理发师说：我给自己理发当且仅当我给自己理发 分析：规则对于“理发师要不要给自己理发”，什么都没有定义，只是给出一个重言式共同的是，对于“理发师要不要给自己理发”什么都没有定义，什么都没有讲。

没有给出定义的两种语句：矛盾式是不懂得如何讲话，什么都没有讲重言式是懂得如何讲话，但讲了一句废话，也什么都没有讲递归函数的例子 例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 ，…） 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)=？ 回答是没有定义现有理论中的对角线方法 在现有数学中，使用对角线方法证明了：实数集不可数 在现有计算理论中，使用对角线方法证明了：停机问题不可计算 在现有递归函数中，使用对角线方法证明了：一元递归函数不存在能行枚举 小结：反证法，假设某前提，然后使用对角线方法得到矛盾从而证明某结论 分析：有一个隐藏的前提是函数处处有定义，然后才得出了矛盾矛盾所揭示的，其实是该点的无定义性计算理论需要更严格的基础 第二次数学危机：微积分刚出现的时候，基础并不稳固dt有时候被当成零有时候被当成非零过了一百年左右，极限理论的出现，为微积分奠定了严格的基础 第三次数学危机：计算科学出现了，基础也还有争议有必要借鉴（潜无穷特征）极限理论，为计算理论提供严格的基础一种构造性的计算理论 将构造主义进行到底 “要证明一个数学对象存在，必须指出这个对象是怎么构造出来的” 函数有不同的层次每一层构造，有每一层构造的游戏规则。

每一层构造，都在更新着“计算”的概念 1、普通的递归函数：f(n)=n+1; 特点：输入任意n，就可以得到输出 该函数已经完成已经确定 2、通用函数：所有一元递归函数 f1 ，f2 ，…定义f(m, n)=g( fm(n) ) 特点：输入任意m和n，还需要先有fm(n)，才可以得到输出 游戏规则已经发生变化：通用函数依赖于一般函数的可数集通用函数的完成与明确，有赖于一般函数的展开与明确 函数作为参数对于“所有”的构造性理解 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(i)=？这时候fi(i)=1-fi(i)。

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