上帝悖论和罗素悖论 罗素悖论和蔡廷常数

2019-02-18 - 罗素悖论

要介绍蔡廷常数,得从常见的的数理逻辑困扰说起。关心台海问题而且了解两岸真实民意走向的人一定知道在大陆青年和台湾青年当中经常会互呛一段话。中国台湾的人会讲:“有种就打过来,你敢打我就敢独立!”而中国大陆的人会说:“有种你就独立!你敢独立我就敢打!”这组对话的内容在逻辑上构成了一个循环,也就是产生了因果关系间的死锁,从而无法推演得出后续结果,所以双方只得维持现状。

上帝悖论和罗素悖论

逻辑体系的推演并不害怕参与要素众多,或者关系复杂,每个要素不管是前有多种原因还是后有多种结果,一般来说整个体系完全可以顺畅的进行逻辑推导。但是有个前提条件,就是整个体系的逻辑结构图中不能出现闭环。闭环意味着逻辑链条构成了循环依赖,推理步骤一旦进行到这里将陷入无法解开的闭锁状态,而这几乎是所有人类所知的逻辑谬误的根本起源。

上帝悖论和罗素悖论

比如很多人所熟知的上帝万能悖论。其内容是万能的上帝能不能造出一块他举不起来的石头?如果神能够造出这样的石头,那么这块石头他无法举起,故此上帝不是万能的;如果神不能造出这样的石头,那他不是万能的。所以无论如何,上帝都不是万能的。从思辨味道上来说,万能悖论的设计思路是符合逻辑缺陷的方向的,但是其表述非常不严谨,以至于使用该悖论本身就是一种错误。

上帝悖论和罗素悖论

上帝万能悖论的主要问题在于它没有事先建立无歧义的明确概念,因此其内容论述基本等同于语言诡辩。在定义不明的情况下,甚至完全不用悖论本身设计的所谓举起和制造这个两难问题,仅凭概念的不确定性就足以驳倒上帝万能。

上帝悖论和罗素悖论

比如,什么事情可以被定义为上帝做不到的事。“举不起石头”这件事,在人类的天然观念中,会被认定为一件上帝做不到的事;然而细想一下,“举起石头”同样可以被认为出现了一件上帝做不到的事。因为人们完全可以把“举不起石头”也看做一种能力,上帝举起了石块,就失去了“不举”的能力。

所以不论上帝做什么,都可以被证明不是万能的。从这些分析可以明白,在严谨的逻辑下,如果未加界定,完成事件A和不能完成事件A都可以作为上帝能力有限的证明。没有概念确立的基础,仅仅凭借“不能举起石头”、“不能制造”这些语句当中的“不”字带给人的否定感受来完成逻辑陈述是没有意义的。

是不是当存在严格准确的概念定义时,就可以避免悖论的出现呢?当然不能!悖论不但存在而且很多,其原因就是出现了定义中的逻辑循环,这其中最有名的便是罗素悖论,其通俗版本叫做理发师困局。一个村子里的理发师定下了一条规矩,他只为本村居民当中所有自己不理发的人理发。于是一个问题出现了,这位理发师是否可以给自己理发呢?

如果他不为自己理发,按照他自定义的规则,他属于自己的服务客户范围,因此可以给自己理发;如果他选择为自己理发,同样按照规则,他便不属于自己的服务对象,因此他又不能给自己理发。面对这个困惑的理发师究竟应该何去何从呢?

和上帝万能悖论一样,仅仅用自然语言讲述理发师困局也是不严谨的。实际上它期望表达的意思体现在集合论中的罗素悖论问题上,这才是一个真正严格的数学悖论。它的出现是由于罗素发现了一个奇怪的集合。

对一个集合而言,有两种不同的类别,一种是集合的全体元素里包含有集合自己。比如集合T定义为“全体非正方形物体组成的集合”,由于T本身是一个集合,不是正方形,所以T自己也应该作为一个元素包含在T中,这类集合叫做本身集合;另一种集合在其所有元素中不包含集合自身。这样的集合最为常见,例如全体整数组成的集合,全体女人组成的集合等等都不允许集合自身成为元素。此类集合叫做非本身集合。

天才的罗素是个奇葩,他是数学出身居然凭借逻辑特长获得了诺贝尔文学奖,正是这个异类的人找到了一个异类的集合:由全体非本身集合构成的集合。这样一来,麻烦又出现了。S自己到底是一个本身集合呢?还是一个非本身集合呢?换句话说S自身是不是S的一个元素呢?

如果假定S是自身的一个元素,则根据分类规定S是一个本身集合,而刚刚说过S的定义是全体非本身集合的集合,既然S是本身集合,所以S应该不是自身元素。这就出现了矛盾。这个两难问题便是罗素悖论。千万不要小看这个悖论,这不是文字游戏,而是真实的基础概念上的重大漏洞。现代数学的整个大厦完全建构在集合论体系之上,如果集合的定义出现了根本性缺陷,将导致严重的后果,这就是著名的第三次数学危机。

其实追究起来,罗素悖论出现的原因并不难理解,它就是在定义上出现了循环。以更方便解释的理发师困局作为说明对象,一个人是否给自己理发是后面理发师发起理发动作的条件和起因,而理发师给一个人理发是他按照条件判断后的的行为。

对其他非理发师的人来说,这个逻辑链条是开放的,但当这两者集中到理发师这个共同角色时,原因和结果构成了逻辑循环,故此出现了困局。要破解这一困局并不困难,只要想办法在不影响其他元素的逻辑结构前提下,引入新的限制打破闭环即可。在罗素悖论中,数学家就是通过引入正则公理,排除了集合可以作为自身元素的可能性,从而解决了数学危机。

图:罗素

停机问题

罗素悖论还有一个常见的在计算机科学中的变种形式叫做停机问题。写过程序的人一定知道一种痛苦,就是程序写好开始运行后等了半天毫无反应,既没有报错,又没有停止,让人不知所措。出现这种情况,一般有两种成因。一是程序运行的时间的确比较耗时,而编程人员又忘记编制任何运行中的动态提示功能,导致机器好像毫无反应。

如果是这种情况,很好解决,只要增加运行中的屏幕提示,比如打印某个变量的状态或计算某种进度即可。但另一种情况会比较麻烦,就是程序执行陷入了死循环,永不停止。如果是这样,那么就必须跟踪查找死循环发生的位置并修改相应程序代码。

因此程序员肯定期望能够有理论大牛发明一个判断程序来提前预报死循环是否会在程序中出现。把一段即将运行的代码作为字符串序列输入到该判断程序中,判断程序直接通过某种算法分析被输入程序的结构,并给出预报结果:该程序可以或不可以在有限时间内完成计算停止。

这就是有名的停机判定问题。这里说的有限时间是一种纯理论概念,一个算法即使所需执行时间要200亿年,超过宇宙的寿命,它在理论上也被认为是可停机的,虽然在实际上这毫无意义。

停机判断程序是否存在呢?答案是不存在。而对于这个不存在性的证明也非常简单,几乎不需要什么数学知识,大致的思路大家都能够明白。假设存在一个这样的判定程序P,将任何一段要运行的程序作为输入参数提交给P后,P可以明确得出输入程序能否停机的判断结果。现在立刻可以利用P构造一个新的反例程序Q,让P程序的判断能力失效。

具体构造方法是,Q中含有两个程序步骤。第一步调用P程序对反例程序Q本身的停机性进行判断,如果判断结果是P认为Q会停机,那么第二步骤则执行一个无限的死循环函数,让程序永不停止;如果判断结果是P认为Q不会停机,则第二步骤中,立刻执行一条终止程序的命令,让程序马上退出。如此一来,无论P做出什么判断,都必然是错的。所以停机判断程序P不能存在。

这个证明过程再说的直白点,就跟一个人和算命的抬杠一样。你说我属虎,我就偏说不属虎;你说我不属虎,我就硬说自己属虎。总之一定能证明算命的说不对。这样的比喻只是一种不严格的证明思路的解释,该问题真正的论证过程是极其严密的,而停机问题背后也是一套成熟的理论叫做可计算性理论。所以用术语来说,停机问题是一个不可计算的问题。

可计算性

人们在最初发明计算机的时候就在思考一个关键的问题:计算机能够处理哪些任务?正是从这个问题产生了可计算性理论。简单的来说,如果一个任务能够在有限时间内通过计算得到答案,就被认为具有可计算性,反之称为不可计算。可计算性问题中最有意思的一个应用是可计算数的提出。

人们发现数字的过程可以说是一个从平凡走向神秘的过程。无理数相对于有理数很奇怪,超越数相对于代数数更奇怪。所谓超越数就是不可能成为某个整系数代数方程的根的那些数,否则就是代数数。一开始人们以为无理数应该都是代数数,以根号2为例,它是代数方程x平方等于2的解,所以根号2是代数数。

可以证明此类平方根都可以写成连分式的级数表达形式,这说明代数数有着较强的规律性。然而1844年,法国数学家发现了第一个不是代数数的无理数。

这个数字整数部分是0,小数点后各位全部由0和1组成。1出现的位置是小数点后第1,2,6,24,120,... 位。这些位置刚好代表着1!,2!,3!,... 。刘维尔证明这个数是一个超越数,它不满足任何整系数多项式方程。

有人会问,怎么没人怀疑e和π不是代数数呢?当然有了,只是一直难于证明,直到刘维尔取得突破后约30年,e被证明是超越数,又过了近10年,π也获得超越数证明。超越数真的很神奇,即使e和π都被证明是超越数,但是它们的和与差是不是超越数,到现在还未获得证明。

如果你觉得超越数已经很超越了,那就错了。更诡异的数在可计算理论提出后被发现,这就是不可计算数。一个数具有可计算性是这样规定的:随便指定一个小数点后的位置,在有限时间内,该数在指定位置之前的各个数位上的数字都能够准确的被计算出来,那么这就是一个可计算数,反之就是一个不可计算数。

圆周率π虽然很奇特,但它所具备的展开式形式让人们可以在有限时间内算到小数点后的任何位置,所以π是可计算的。而不可计算数的最典型的例子是1975蔡廷提出的,当时他恰好在研究停机问题时,故此这个数叫做蔡廷常数,也叫做停机概率。

刚才已经证明,停机问题是不可计算的。人们无法编制一套算法准确的预测出一个程序可否在有限时间内终止。但是数学家就是作,面对这个已被证明的结论还是不死心。蔡廷想,虽然不能准确预测出程序是否一定终止,但是预测它终止的概率是不是可行呢。

任何一段程序运行的结果,只有终止和永不终止两种情况。所以在全体可能的程序当中,包括那些杂乱无章的乱码程序也算在内,必然是一部分的运行结果为终止,一部分的运行结果为不终止。可终止程序的数量一定占有全体程序总数的一个固定比例,所以停机概率一定存在,它的上限为1,下限为0。

不过在真实环境中,一种语言书写的程序有无穷多个,故此要想用统计方法得到这个概率值,需要进行的程序测试也是无穷多次,显然这是完成不了的。停机概率存在但不可计算,就这样第一个不可计算数蔡廷常数Ω被发现了。

蔡廷常数Ω虽然不可计算,但对它性质的分析仍然不少。在《思考的乐趣》一书中作者提供了一个超赞的蔡廷常数的理想应用:利用Ω能够建立一套万能证明法,证明前面说的众多的数论难题,却完全不需要拥有复杂的数论知识。这听起来简直是天方夜谭,但是这的确是真实的。只不过要声明一点,这是说的理想应用是头脑中的想象方案,和爱因斯坦的追光实验一样,不具备可计算性。

下面我们就来说说这个万能证明法。怎么才能证明哥德巴赫猜想呢?用陈景润那样的筛法当然有可能?但其实完全可以打开脑洞换一个思路。哥德巴赫猜想是说任何一个大于3的偶数可以分解成为两个质数之和,对此类以自然数为命题的猜想最直觉的冲动就是挨着试,用穷举法从4开始一个个偶数试下去看能不能拆成两个质数。

但问题是这样的偶数无穷多,穷举是不能穷尽的,你试了前面再多的偶数,也不能保证后面没试到的偶数一定满足猜想,所以穷举法无效。

但是有了停机问题后,神奇的转机出现了。如果我们编制一个程序,从4开始逐个遍历全部偶数,逐个测试当前偶数可否拆分成质数对儿。如果测试成功,继续测试下一个偶数,如果不成功,终止程序。这样一来,只要证明该程序永不停机,也就等于证明了哥德巴赫猜想。同样的道理,所有的以遍历自然数的性质为命题的数论猜想全都可以用相应穷举程序的不停机性来加以证明。所以这是一个名副其实的万能证明法。

理想停机判断法

但停机问题是一个不可计算问题,所以想通过证明穷举程序不停机来等价的证明哥德巴赫猜想等难题这条路在实际上是走不通的,但这不妨碍我们继续进行该问题的头脑风暴。

假设我们有无限长的寿命和无限多的计算机,我们可以用逐一检测全部程序的方式来逐渐统计出停机概率。因为停机概率就是一个分数值,分子记录测试中出现过的不停机程序的总数量,分母记录已经检测过所有程序总数量。因此,每当新出现一个不停机程序时,分子分母同时加1,停机概率增加,Ω得到一点正贡献;如果新出现一个停机程序时,分子不变,分母加1,停机概率减小,Ω得到一点负贡献。

就在正负贡献波动中,停机概率会接近蔡廷常数。

现在我们把这种测试的顺序组织的更有秩序一些,分组进行。根据每个程序字符串的长度,把全体程序分成长度为1,2,3,...,n的各类,每种类别都对应一个自己组别的停机概率P1,P2,P3,...。分组概率Pn代表了所有长度为n的不停机代码所积累的正贡献。

如果用一个自然数k,把这些分组概率分成两段:前k项和大于k的无穷多项。数学上可以证明,后面的无穷多项的贡献会随着k变大而逐渐接近于0。也就是说,当代码长度非常大时,不停机代码带来的贡献越来越接近于无。有了这个性质,可以大胆设想出如下的理想停机验证方法。

设一段待验证的程序长度为L,找到一个足够大的k,让k后面无穷多项的总贡献比验证一个L长度的代码为停机程序时给Ω带来的贡献还要小。这意味着,此时后面无穷多项带来的波动已经比不上当前一个程序为Ω带来的贡献波动了,因而后面的无穷多项可以忽略不计,只要考虑有限的前k类代码即可。此时问题变成了有限问题,得到了简化。

接下里用穷举算法生成所有长度不超过k的代码(这点很容易),然后同时运行这些程序。随着运行时间的延长,越来越多的程序将会因运行结束或者出错而停机,Ω将会从初始值1一路下降。但是由于蔡廷常数的存在,Ω是有下限的,停机程序的出现数量也会越来越少。

一旦当欧米伽值和前k项累积概率的差开始小于一个程序带来的贡献波动值时,就可以宣布,此时还没有结束运行的程序将会永远运行下去。因为此时欧米伽和下限之间的误差已经容不下再产生新的停机程序了。

总结起来,利用蔡廷常数的理想停机验证法,就是首先选择一个足够大的有限程序集合,近似等同于全体程序集合。然而同时运行有限集合中的全部程序,当陆续停机的程序带来的负贡献值使得停机概率下降到与下限之间的误差已经容不下再新增一个停机程序带来的贡献波动时,还未停止的程序一定就是不停机的。

想想看,这味道是不是很像我们的反分裂国家法。反分裂国家法规定的启动条件有三:1,台湾独立成为事实;2,可导致独立事实的事变发生;3,永远失去和平统一的可能。从数学观点来看,前两条是把台湾独立和武力统一两种状态进行了等价定义,所以启动反分裂国家法的关键就在于台海目前维持现状的程序运行是不是一直不停机。

我们形式化的认为台海问题的发展是一台超级复杂的政治经济计算机的运行,台海问题所有的输入信息是台湾总统府和中共中央军委全部的政策文件,任何一个文件的出台相当于为这台计算机输入了待判定程序。在这种形式化的框架下来看,所谓台海问题就是一个特殊的停机问题。大陆需要研判目前运行的程序究竟是否会在有限时间内停止。如果是永不停机,那就是永远失去了和平统一的可能,则反分裂国家法便会启动。

问题是如何判断台海程序的停机性呢,其思路正好是上述的理想实验测试法。将所有的可能手段同时加以运行,政治、军事、文化、经济各种手段,如果运行足够长的时间,当所有的和平手段纷纷停机无效时,基本就可以判断出维持分离现状状态的程序将永不停机。

好消息是,蔡廷常数已经算出的有限位数值约为0.007875,所以有理由相信台海常数也不会大到哪里去,这意味着维持现状并不见得会有很大概率。当然如果最后台湾真的不停机,那剩下的结果大家也都清楚,电脑程序不愿停,就只有拔插销了。

创业不易,耳娱心憩之余如有您偶或中意的节目期次,请帮我们随手转发。书不尽言!您的鼓励是我们最大的动力。谢谢!

相关阅读
罗素悖论的启示罗素悖论的启示 罗素悖论的由来

一天,萨维尔村理发师挂出一块招牌:“村里所有不自己理发的男人都由我给他们理发,我也只给这些人理发。”于是有人问他:“您的头发由谁理呢?”理发师顿时哑口无言。因为,如果他给自己理发,那么他就属于自己给自己理发的那类人。但是,招牌上说明他不给这类人理发,因此他不能自己理。如果由另外一个人给他理发,他就是不给自己理发的人。

罗素悖论的内容罗素悖论的内容 罗素悖论 简单介绍一下

罗素悖论的事情大家知道吗?可能有很多人都不知道罗素悖论是什么意思,罗素悖论其实就是我们常说的理发师悖论、书目悖论,下面我们就来了解一下。罗素悖论罗素悖论罗素悖论:设集合S是由一切不属于自身的集合所组成,即“SxxS”。那么问题是:S包含于S是否成立?首先,若S包含于S,则不符合xS,则S不包含于S。

罗素悖论的影响罗素悖论的影响 为什么有人说罗素悖论动摇了整个数学的基础?

维特根斯坦:“不被任何人理解是非常痛苦的。”1、关于理发师悖论在一个村子里有一位理发师,这位理发师声称:“给而且只给那些不给自己理发的人理发”。现在问理发师是否要给自己理发。如果理发师不给自己理发,那么根据定义,他要给自己理发;如果理发师给自己理发,那么根据定义,他不能给自己理发。这就是著名的“理发师悖论”。

罗素悖论的意义罗素悖论的意义 2016高考数学:一个故事让你理解罗素悖论

在某个城市中有一位理发师,他的广告词是这样写的:本人的理发技艺十分高超,誉满全城。我将为本城所有不给自己刮脸的人刮脸,我也只给这些人刮脸。我对各位表示热诚欢迎!来找他刮脸的人络绎不绝,自然都是那些不给自己刮脸的人。可是,有一天,这位理发师从镜子里看见自己的胡子长了,他本能地抓起了剃刀,你们看他能不能给他自己刮脸呢?如果他不给自己刮脸。

罗素悖论解释罗素悖论解释 读维特根斯坦(罗素悖论)

3.332何命题都不可能述及自身,因为命题指号不可能包含于自身(这就是全部的类型论)。当我们说“太阳”或者“张三”到底是什么意思呢?按照维特根斯坦的解释,那不过是一个指号,指向那个我们能够有经验的东西。太阳在英语里是“sun”,张三也许有另一个称呼,比如张教授,没有关系,因为那个词有意思不是其本身,而是它们代表了某个东西。

推荐阅读
什么是黄金分割率什么是黄金分割率?黄金分割率是什么意思?
罗素悖论理发师罗素悖论理发师 罗素悖论 它与理发师理论是等价的
魏书生人物事迹魏书生人物事迹 魏书生的做人哲学
水上乐园大作战【水上乐园大作战】水上乐园作文400字4篇
公务员报考单位选择公务员报考单位选择 公务员报考什么单位好?
南京大学商学院南京大学商学院 2018'南京大学商学院新年论坛圆满落幕
鲁能塔尔德利鲁能塔尔德利 塔尔德利时隔115天再破门 离开鲁能后首次得分