庄朝晖，厦门大学计算机科学系
第五届两岸逻辑教学与研究学术会议，重庆，2012年4月28日--2012年4月29日 前言：对角线方法
...以下问题密切关联：
罗素悖论等诸多悖论；
康托尔对角线方法；
哥德尔定理；
图灵理论的停机定理等不可计算问题。
...这些定理都使用对角线方法，如此得到矛盾。
...主流的处理方案：如果可以找到可以否定的前提，就将错误归为该前提的错误。
...本文将给出另外的分析。
一、理发师悖论
...理发师悖论：在一个小镇上有一位理发师，这位理发师遵守这样的规则：“给而且只给那些不给自己理发的人理发”。现在问理发师是否要给自己理发，这时候出现悖论。
...主流的（蒯因）解决方案：不存在这样的理发师。或者，不存在能够遵守该规则的理发师。
...奇怪之处：逻辑推理居然可以证明一个经验问题。过分夸大了逻辑的作用。
...对于理发师悖论的可能证明过程：假设有如此一位理发师。如果他要给自己理发，根据他的规则，他不给自己理发。如果他不给自己理发，根据他的规则，他要给自己理发。矛盾。因此假设不成立，如此一位理发师不存在。
...这样的证明过程是可疑的。以下我们进行新的分析。
...理发师的规则，对于他人都是没有问题的。问题发生在对于自己。以下是简化版。
对于理发师悖论的分析
...例1：理发师说：我给自己理发当且仅当我不给自己理发。 （在保留特征后的简化版）
...可能解决方案是：不存在能遵守该规则的理发师。这样的解决方案是有些奇怪的。
...本文的方案：规则对于“理发师要不要给自己理发” 没有定义，只是给出了一个矛盾式。如果认为存在定义，就会产生矛盾。
...两种方案比较：本来没有规则，谈不上有没有能守规则的人。本文的方案更根本。
...矛盾出在概念层面，而不是在经验层面。
...例2：理发师说：我给自己理发当且仅当我给自己理发。
...分析：规则对于“理发师要不要给自己理发”，什么都没有定义，只是给出一个重言式。共同的是，对于“理发师要不要给自己理发”什么都没有定义，什么都没有讲。
...没有给出定义的两种语句：矛盾式是不懂得如何讲话，什么都没有讲。重言式是懂得如何讲话，但讲了一句废话，也什么都没有讲。
递归函数的例子
...例3：定义f(x)如下
f(a)=f(a)
分析：f(a)的值其实没有定义。
...例4：定义f(x)如下
f(a)<>f(a)
分析：f(a)的值其实没有定义。如果认为存在定义，会产生矛盾。
...例5：定义f(x)如下
f(a)=1-f(a) 当x=a，
f(x)=0，其他情况
...分析：f(a)的值其实没有定义。如果认为存在定义，会产生矛盾。
...理发师貌似给出对于所有人的规则，然而事实上，他并没有给出对于自己的规则。
...对于自己，他只是给出了一个矛盾式，没有定义。
...解决理发师的悖论很简单，理发师先前给出的规则，对于他人都是可以适用的。理发师只需就关于自己的部分重新制定一下规则。
...此方案的优点：消除了该消除的，保留了该保留的。
二、康托尔对角线方法
...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=(1, 0, 1……)（康托尔数）。
...一般地，定义E0=(b1, b2, b3…bi…) ，其中b1与a1.1不同, b2与a2.2不同……
...E0也是M中的元素。现在，不妨设E0等于某一个Ei。然而，根据E0的定义，bi与ai.i不同，因此E0不等于Ei。矛盾。
...因此，假设是错误的，集合M是不可数的。因为集合M与实数集之间可以建立一一映射，因此实数集也是不可数的。
对于对角线方法的分析
...在康托尔证明中，在实无穷的意义，对康托尔数进行了定义，并且在已完成的意义上来使用康托尔数，才导致了矛盾的产生。
...“所有”的两个部分，“已展开”部分和“未展开”部分。在证明中，被混为一谈。
...在康托尔证明中，bi的值除了0和1，还有一个可能是没有定义。（bi的值依赖于bi的反）
...一个隐含前提是，在该点有定义，从而导致矛盾的出现。所以，矛盾得到的结论应该是：在该点没有定义。
递归函数形式
...设M为所有如下函数：N-->{0, 1}的集合。
...可以将M的元素表达成如下的形式：(x1, x2, x3, x4……) （其中的xi是0或1）。
...例如，
f(1)=0
f(2)=1,
f(3)=0，
f(4)=1
……
...可以将f表达如下形0,1,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=(1, 0, 1……)（康托尔数）。
...一般地，定义E0=(b1, b2, b3…bi…) ，其中b1与a1.1不同, b2与a2.2不同……
...E0也是M中的元素。现在，不妨设E0等于某一个Ei。然而，根据E0的定义，bi与ai.i不同，因此E0不等于Ei。矛盾。
...因此，假设是错误的，集合M是不可数的。
对角线相关悖论的特点
...基于可数集，在实无穷的意义上，定义一个与集合中所有元素不同的元素。然后，又认为这个元素也是在可数集之中。如此，产生矛盾。如果可以找到可以否定的前提条件，就将矛盾的责任归于该前提。
...本文则认为，矛盾是来源于误用新元素的规则。新元素的规则，不一定处处有定义。
...这个新元素与其他元素不同的地方在于，它是基于可数集定义的。给定可数集的一个元素，这个新元素才得以继续展开一位。
三、停机定理的证明
...证明方法与康托尔对角线定理类似。
...在图灵计算理论里，证明了停机定理。
...在递归函数理论里，也证明了类似定理。
...关于对角线证明出来的定理，维特根斯坦评论为：“夸大的证明”。但他的观点长期被忽视。
四、矛盾可以说明什么
...《韩非子》里有这样一个故事：楚人有鬻盾与矛者，誉之曰：“吾盾之坚，物莫能陷也。”又誉其矛曰：“吾矛之利，于物无不陷也。”或曰：“以子之矛陷于之盾，何如？”其人弗能应也。
...我们读完这个故事，并不会认为，这位楚人不能存在，或者更荒唐地认为，《韩非子》这本书并不存在。
...我们只能说：书中这位楚人说的话里面有矛盾。因此，这位楚人应该修改他的话。
逻辑的功能与局限
...逻辑是已有知识的符号表达，在演绎封闭的意义上，逻辑并不能发现新知识。从信息的角度来看，演绎推理并不能增加信息量。这是由演绎推理的保真性决定的。
...同样，逻辑矛盾并不能用来发现新知识。逻辑矛盾揭示的是已有概念间的矛盾，已有概念要进行修改或限制。
...当我们向左走的时候，如果碰壁我们可以说左边走不通，但是这并不能证明向右可以走得通。
五、一种构造性的计算理论
...将构造主义进行到底：“要说明一数学对象存在，必须指出这个对象是怎么构造出来的”
...对于一个函数，已构造部分才是有意义的，未构造部分是无定义的。
...函数有不同的层次。每一层构造，有每一层构造的游戏规则。每一层构造，都在更新着“计算”的概念。
...1、普通的递归函数：f(n)=n+1;
...特点：输入任意n，就可以得到输出。
...该函数已经完成已经确定。
...2、通用函数：所有一元递归函数 f1 ，f2 ，…定义f(m, n)=g( fm(n) )
...特点：输入任意m和n，还需要先有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)自身，这是没有定义。
...对于这个函数而言，至少在这一点上是没有定义的。
对于“所有”的构造性理解
...这里的“所有”，如何理解？
...实无穷理解：f已经完成的，已经明确。存在一个康托尔函数与所有一元函数都不相同。
...潜无穷理解：不断展开的，f的意义必须伴随着 f1 ，f2 ，…的展开而不断展开。所有已经展开的一元函数, 都存在一个函数与之不同。
“相互追随，趋于无穷”
不停机不可以吗？
...不停机有两种：一种是无意义的死循环，这种不停机意义不大。
...但是，还有另外一种不停机。比如不断计算PI的更精确值的程序。比如通用图灵机——计算机。
...大脑，在某种意义上，也是一种通用图灵机。难道大脑也要停机才有结果吗？
...所谓的停机，其实只是相对于那个计算需求而言。如果得到了需要的结果，这时候可以说这次计算停机了。
...我们关注的是问题有没有得到解决，停机不停机又有什么关系呢？
...一般函数与通用函数有不同的使用规则，当前计算理论却往往混为一谈。
...应该分开一般函数与通用函数，来分析停机问题和递归定理。
六、逻辑层面的应用
...对逻辑的构造理解：重视逻辑的构造成分。
...两种“所有”：一为定义上的“所有”，比如“所有鸟都是动物”，这里的“所有”可以包含未来的鸟。二为归纳上的“所有”，比如“所有鸟都会飞”，只包含过去经验到的鸟。
...经典一阶逻辑没有区分两种“所有”。
七、概念层面的应用
...构造概念论：对于概念的构造理解。
...概念是对于过去经验的概括。经验一直在变化之中，概念也是一直处于变化之中。
...概念主义所说的本质的“概念”，如果不是指已知的经验，那么就没有实际的意义。
结论：将构造主义进行到底
...理发师悖论的原因是，理发师对于是否给自己理发没有给出定义。
...对角线悖论的原因是，对于“所有”进行实无穷理解，在已完成的意义上来使用康托尔数。
...逻辑矛盾揭示的是已知概念框架的矛盾。逻辑并不能用来发现新知识。
...构造性计算理论：对于“所有”的构造性理解；对于函数的构造性理解。
...逻辑层面的应用：“所有”有不同的使用方法。
...哲学层面的应用：对于概念的构造性理解（构造概念论，消解概念主义）。
相关研究工作
...关于对角线方法和哥德尔定理：《基于直觉主义对哥德尔不完全性定理的评论――从维特根斯坦的评论开始》，发表在《厦门大学学报（哲社版）》，并以此文获得“首届洪谦哲学论文奖”。
...关于对角线方法和悖论：《基于对角线引理和维特根斯坦思想对于悖论的分析》，发表在《中国分析哲学 2010》
...关于对角线方法：《Wittgenstein's analysis on Cantor's diagonal argument》，发表在2010年第七届国际认知科学大会。
谢谢诸位老师！
[返回] 计算机科学论坛 →
计算机理论与工程 → 『 理论计算机科学 』 → 关于对角线方法和停机问题的评论 [原创]
(订阅本版)
2012/5/6 23:43:00
新浪微博
关于对角线方法和停机问题的评论 [原创]
