planeheart的头脑风暴
注册日期:
2013-09-16 15:53:09
上次登录:
2016-05-11 02:38:27
邮件地址:
saintpal@163.com
兴趣领域:
数学,物理,人工生命,系统科学,计算机科学
  
利用Martin-lof随机性改造证伪主义
2014-01-14 14:15:03  科学哲学  证伪主义  随机性  算法熵 
相信列位都对波普尔的证伪主义主张有所了解。概括而言,该主张认为:
一个理论是科学的,因为它可以被证伪。
该主张的关键论据之一在于证实和证伪的不对称性。其论证大致如下:科学命题都是全称命题,而全称命题的证实都是极度困难的,而证伪则相对容易。作为一个例子:天下乌鸦一般黑的主张,只需一只白乌鸦的存在就能否定。
基于该主张甚至可以得出一些看似合理的结论,例如:若我们从黑箱中摸球,前面100只摸到的都是红球,那么以下两个假定(均与目前的观察结果吻合):
“(1)黑箱中都是红球”
,(2)黑箱中存在各种颜色的球‘
中,我们更应该接受(1),因为这样使得理论显得简单且更容易被证伪。(波普尔认为,归纳推理对科学而言是不必要的,原则上可以用证伪主义的原则来选择接受的理论)容易看出,如果第101只球是绿球,那么(1)即被证伪,但(2)并没有被证伪,所以(1)具有更强的可证伪性。
通过一些粗糙的类比推理,证伪主义理论还能以一种诡异的方式和奥卡姆剃刀取得共鸣,即:简单的理论倾向于极端,也即是容易证伪。因此通常应该选择尽可能简单的理论。

证伪主义理论本身在科学哲学领域也饱受批评,在此不提。因为本文作者认为这些批评没有击中这个理论真正的要害,也没能找到足够好的弥补方式,真正的问题在于:
它试图主张的证实和证伪的不对称性其实在科学中是不存在的。其错因在于其前件”科学命题都是全称命题“并不正确,显然,”二维强关联体系中允许存在不服从玻色和费米统计的准粒子“并不是全称命题,而且刚好相反,这类命题的证伪极度困难,而证实相对容易。这使得证伪主义相对于实证主义的所谓优势丧失殆尽。
甚至用减弱的版本说”作为科学理论的基本原理必须是全称命题““也不正确,因为实际上允许我们用特称命题的形式来表述其中一些原理,例如,存在完备描述物理体系的拉格朗日函数。即便依然存在不少似乎只能以全称命题形式出现的原理,也很难看出以后不存在改造表述的可能性。更重要的是,全称命题通常很难证实,但并非一定不可能证实。
证伪主义者将证实全称命题的难度上升为”不可能“的理由是认识对象的无限性,但是这种无限性本身就不是能从纯粹的演绎推理中得出的结论。(天下的乌鸦数目确实不是无限的)这导致他们背离了原有的主张。而关于物理中可以被称作”认识对象“的数目是否为无限,尚存在严重的争议。(如果将贝肯斯坦极限用于可观测宇宙整体,那么用于描述它的最低信息量,以bit计,是有限的)
因此,实际上证伪主义者的自相矛盾发生在他们试图论证科学命题的特性的过程中,没有成功地从纯粹逻辑的角度支持他们的论点,却主张他们的论点不依赖归纳。


因此本文作者打算从随机性,而非可错性的角度来看整个问题。
所谓算法熵,即一般信息论教材所称“科尔莫格洛夫复杂度
Martin-lof随机性是对无限长的0-1二元序列定义的。对于有限长的0-1序列,因为算法熵的定义依赖于通用机U的选取,因此该定义对有限序列的存在局限性:结果依赖于对U的选取。然而对无限长的序列,选取任意U均会给出相同的结果(这称作算法熵的普适性),因此,该定义虽然需要提及通用机,但本质上不依赖通用机。
该随机性的确具有非常有趣的不对称性:
(1)我们可以证明绝大多数的序列是随机的。(确切而言,非随机的序列构成零测集)
(2)我们可以证明某一个特定的序列不是随机的(例如010101……的循环序列)
(3)我们不能证明某一个特定的序列是随机的(这有点像这样的例子:根号2在二进制下的表达的前N位,很难将它和用抛硬币得出的0-1序列区分开来)
其中(3)由Chaitin不完备性定理所保证(此人定义了著名的Chaitin常数):
任意公理化形式系统A,均存在常数L,使得我们在A中无法对任意s证明K(s)>L
因此,这种不对称性如果被用于替代原有证伪主义理论中的证实-证伪不对称性,将比原本的论证更加可靠,因为它不依赖于可疑的”认识对象的无限性“这种外加的东西,而是来自于普遍存在于任意公理化形式系统中的不完备性(或者说,哥德尔不完备性的一部分)。
我们很容易发现这个论证用于说明原本的例子会比证伪主义理论做得更好,而且它反映”人类偏好简单理论“的方式更加自然。因为粗略地说,算法熵对应着描述的复杂度。在前面的论证中,接受”(1)黑箱中都是红球“的理由现在是它比”(2)黑箱中存在各种颜色的球“的算法熵更低,因此更远离“随机”。从观察到有限数目的黑乌鸦而得出“天下乌鸦一般黑”的缘由也是同理的。在这个理论中,人类追寻科学真理的目的被归结于从混沌的宇宙中构建秩序,以避开知识体系由“完全随机”支配的可能。
让我们考虑一个简单的由无限0-1二元序列组成的宇宙(实际上,或许对于一台计算机而言世界就是这个样子)。当我们连续观察到前面的10000个1(prefix)的时候,尽管依然存在不可数无穷多的以这样的10000个1为前缀的随机序列,依照传统的波普尔理论来看,这些“竞争理论”将会使认为“该序列全为1”的简单理论具有0概率,然而利用算法信息论的世界观则不会如此。由于我们无法证明这样的序列是高算法熵的随机序列,所以,我们应该选择低算法熵的假定,即认为该序列中应该全为1 。
(或者,利用算法信息论中“普适概率”的概念则更为明晰,尽管{全体0-1序列}是不可数集,但这里所有的随机序列被赋予0概率,而算法熵较低的序列则具有较高的概率)
利用以上的方法建立模型的理论已经存在了,这就是所谓“最小描述长度”(MDL)准则。然而将这种理念推广到一般还存在巨大的困难,由于:(1)算法熵的不可计算性。(2)对一般的认识对象,而非二元序列或者整数等数学对象,很难定义算法熵(Zurek提出了将算法熵用于物理描述的可能性,并认为它实质上与物理学中的吉布斯熵存在对应关系,这便是本文沿用其说法将其称作算法熵,而非科尔莫格洛夫复杂度的理由)。然而,证伪主义理论中“时空区域的无限性”等说法同样是高度可疑无检验性的表述,因此我以为这样的改造能够在保留其初衷(证明一个命题及其反面的不对称性)的前提下,修正其偏激的段落。
2014-01-15 01:38:54
   是原创的吗?好文!
为什么对于无穷序列,它的复杂度不依赖于通用图灵机?

2014-01-15 04:10:37
   回楼上jake:
非常简单,因为算法熵的通用性。
对于二元序列s,记利用通用机U定义的算法熵为K(s|U),则在任何图灵机A下定义的算法熵K(s|A)均有
K(s|U)<=K(s|A)+CA,其中CA是只依赖于A的常数。
证明:一种让U输出s的办法是输入指令(假定其长度为CA)令U模拟A,然后输入在A上输出s的最短程序,根据算法熵的定义,后者的长度等于K(s|A)。
因此,在U上能够输出s的最短程序长度(即K(s|U))不应大于K(s|A)+CA。证毕。
无限序列的随机性做如下定义:

”若存在常数c,使该无限序列的任一有限前缀(prefix)s均满足K(s|U)>|s|-c,则称该序列为随机的。
|s|为序列的长度。


假如存在两台通用机U1和U2,序列D为在U1的意义下的随机序列,即D的任一有限前缀均有
K(s|U1)>|s|-c
由算法熵的通用性,
K(s|U1)<=K(s|U2)+CU2
K(s|U2)>=K(s|U1)-CU2>|s|-c-CU2
记C=c+CU2,则C使得D的任一有限前缀满足随机序列的充分条件,D在U2的意义下亦为随机序列。
故随机序列的定义不依赖于通用机的选取。
2014-01-15 07:17:54
   赞
2014-02-21 06:48:38
  

从另外一个角度来看一下二元字符串的随机性:
这里把文中关于随机性的不对称性的三个问题分为两个说明,把(1)和(3)归为一个问题。【关于问题(2)此处不论。】

对于任何能写出或数学描述的有限、无限的二元字符串,在可定义变换规则下(如指定的进制),可对应一个相应的实数,反之亦然。故有给定定义下二元字符串与实数的一一对应。
因此一个任意二元字符串或者对应一个超越数,或者对应一个代数数。假设任意二元字符串对应一个代数数,则该“任意”二元字符不是随机的,它必是某一个整系数代数方程的根,被那个方程所“制约”。(该二元字符串的“果”被变量的N次方的递增和和N+1个整数的关系--“缘”所制约,这便是其“因”,否定非随机意义。这就是局域性的“缘起性空”,空间的本来面貌嘛,呵呵。)如果该二元字符串不是代数数,它便是超越数。超越数是一个不可数集,其势大于代数数集。也就是说实数域内,超越数远多于代数数。那么超越数是随机的吗?Liouville常数,e,π等超越数显然不是,因为它们可以从一个已知的规则之下导出。那么e+π是超越数还是代数数?现在还没人知道。对于那些大量的神秘的超越数,我们所知甚少。实际上,在希尔伯特著名的23个数学问题中,第7个问题就是关涉超越性的证明。至今为止,Gelfond-Schneider也只是告诉了我们如果α是代数数(不等于0和1),β是无理数的代数数,那么α的β次幂是超越数。
 但如(e+π),因为e,π不是随机数,所以(e+π)是也非随机数,由于不知(e+π)是代数数还是超越数,故我们可以推知,我们不能有效判定一个非随机数是超越数还是代数数。或者说,除非我们能找到证明超越数的万能公式,我们有一种规则能写出或数学描述出所有超越数,否则我们就无法判定那些潜在的超越数的随机或非随机性。如果我们能找到如描述代数数那样的通项表达,那么就不存在任何随机存在的“任意二元字符串”,一切皆必然。但显然,决定超越数的“缘”(如果普适性存在的话)与决定代数数的“缘”是如此不同,空间关系泾渭分明。从哲学直觉的角度来看,要完成统一的任务几乎是不可能的,但如哥德尔似的思维一样,这却是不可证的。
  因此(1)和(3)可描述为:对于绝大多数二元字符串序列,是随机的还是非随机的是不可判定的。

2015-07-02 14:58:33
   搜索超循环轮进入了这里,发现知网2000年后发的论文都是草包。虽然我学农
登录后才可以评论,马上登录