通用计算——计算通用
通用计算：起源于莱布尼兹，将各种问题符号化数字化之后，进入计算过程。
计算通用：万物之所以可以计算，是因为万物本来就是在计算。区别只是在于是不是使用数字进行计算。
一切皆计算……
将构造进行到底
计算科学的特点是：构造性，能行性和潜无穷。
然而计算理论的研究框架却具有以下的特点：非构造性，非能行性和实无穷。例如数理逻辑的语义部分，例如计算理论的停机问题等等。
提出的问题：有没有另一种可能性，使用构造性的框架来思考构造性的计算科学。
回顾历史
为了重新思考计算理论，有必要回顾计算科学历史。
罗素悖论引起了第三次数学危机，在这次危机中走出了计算科学。
康托尔对角线方法
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 ，…的展开而不断展开。所有已经展开的一元函数, 都存在一个函数与之不同。
“相互追随，趋于无穷”
不停机不可以吗？
不停机有两种：一种是无意义的死循环，这种不停机意义不大。
但是，还有另外一种不停机。比如不断计算PI的更精确值的程序。比如通用图灵机——计算机。
大脑，在某种意义上，也是一种图灵机。难道大脑也要停机才有结果吗？
所谓的停机，其实只是相对于那个计算需求而言。如果得到了需要的结果，这时候可以说这次计算停机了。
我们关注的是问题有没有得到解决，停机不停机又有什么关系呢？
一般函数与通用函数有不同的使用规则，当前计算理论却往往混为一谈。
应该分开一般函数与通用函数，来分析停机问题和递归定理。
小结
将构造进行到底：计算科学独立出传统数学框架。
逻辑矛盾揭示的是已知概念间的矛盾。逻辑并不能用来发现新知识。对角线，哥德尔定理，停机问题证明中出现的矛盾，揭示的是思维中的某些混乱。
对于“所有”的构造性理解，对于函数的构造性理解，对于概念的构造性理解。
更无争议的计算理论基础：直觉主义与形式主义之间的第三种可能。
不可计算问题的再思考：停机问题等。
谢谢诸位老师！
附录：对角线引理
1962年，汤姆森（J.F. Thomson）发表论文“论几个悖论”，令人信服地显示所谓的语形悖论和语义悖论实际上有共同的结构，都与康托尔对角线方法有密切的关联。
他基于康托尔对角线方法，提出对角线引理。汤姆森成功地将罗素悖论、格雷林悖论和理查德悖论等表达成对角线的形式。
以下，我们来思考一下对角线方法。
康托尔对角线方法
1891年，康托尔使用对角线方法证明：实数集是不可数的。以下是证明过程。
设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。矛盾。
因此，假设是错误的，集合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等于某一个Ei。根据E0的定义，bi与ai.i相同，也就是说Ei的第i位定义为与自身相同。这时候，可以认为bi是没有定义的。因为这时候，这个规则说的是：“做与你所做的相同的事情！”，相当于什么都没有说。
从以上的正对角线方法，很清楚地可以看出，Ei的第i位是没有定义的。这个性质不妨称为定义的“不完整性”。
定义的不完整性
正对角线方法与逆对角线方法是相似的，都具有定义的“不完整性”。
维特根斯坦曾经问道：“为什么矛盾比同义语反复更加令人害怕？”
维氏对于其他悖论的统一分析
维特根斯坦虽然没有像汤姆森一样提出明确的“对角线引理”，但我们在他的著作中可以发现，他对于对角线相关悖论的分析方法也是一致的。
在分析罗素悖论时，维氏说：“矛盾的根源在于把函项作为自身的函项。这种矛盾的结果意味着，‘f’永不能作为一个论证用在‘f(x)’中。……你可以说‘f(f)’是没有意义的，或者说括号外的‘f’代替着更高阶层的函项。”
维氏在分析“说谎者悖论”的时候说：“这语句本身是没有用的，这些推论也同样是这样”
在分析格雷林悖论时，他说：“在这里，‘这种矛盾是真的’意味着它得到证明；它是从对‘h’这个词的规则中推寻出来的。它的使用正要表明，‘h’是一个词，这个词在被置于“ξ∈h”之中时不会产生任何命题。”
对角线相关悖论的特点
基于可数集，在实无穷的意义上，定义一个与集合中所有元素不同的元素。然后，又认为这个元素也是在可数集之中。如此，产生矛盾。如果可以找到可以否定的前提条件，就将矛盾的责任归于该前提。
本文则认为，矛盾是来源于误用新元素的规则。新元素的规则，不一定处处有定义。
这个新元素与其他元素不同的地方在于，它是基于可数集定义的。给定可数集的一个元素，这个新元素才得以继续展开一位。
结论
当我们给出规则的时候，规则并不一定处处有定义。如果我们认为规则处处有定义，这将会导致矛盾。矛盾的起因是：规则并不一定处处有定义。
在维氏看来，悖论往往是思维混乱所产生，起源于逻辑或者规则的误用，起源于语言的误用。
悖论其实并不可怕，关键只要将错误的逻辑和规则使用看清楚和限制住就可以了。
数学历史上一个例子是0除0的除法。如果根据a*b=c来定义c/a=b，那么就可以得出2=0/0=3。矛盾。但这个矛盾并不可怕，它只是说明我们的除法规则需要完善。所以，数学家们规定0除以0是没有意义的。
同样地，在我们的悖论中，只要看清并限定：这里的规则用于自身时是没有定义的。
如此，既保留了规则的有用成分，又排除了规则的误用成分。
[返回] 中文XML论坛 - 专业的XML技术讨论区 →
计算机理论与工程 → 『 理论计算机科学 』 → 一种构造性的计算理论[原创]
(订阅本版)
2011/4/15 18:26:00
新浪微博
一种构造性的计算理论[原创]
