从AIT看不完全PPT课件

1、从从AIT看不完全看不完全李熙1什么是什么是“随机随机”？不可预测。不可压缩。能通过统计学上的检测。2几个例子几个例子111.10.12345678910111213140.141592600100100001111110110101010001000001110110101011010000100100001113一、预备一、预备= 0,1=?,0,1,00,01,10,11,000,001集合S是prefix-free的如果对于任意的s,tS，不存在s是t的prefix的情况。约定：后面提到的所有机器默认的作用程序集合皆为prefix-free。是r.e. 如果它是一串递归不降有理数数列的

2、极限。4是computable如果存在递归的有理数数列ann使得对任意n ，|-an|2-n。约定将一个实数与其二进制展开式等同视之，即=0.a1a2a3an其中i0,1。n表示序列前n项a1a2a3an 。一个实数序列ann是computable如果存在全递归函数f使得对任意m,n ， |an-f(n,m)|2-m5二、算法复杂性二、算法复杂性机器U为通用机如果对于任意机器C存在常数c对所有的s、t，若C(s)=t则有s，|s|s|+c且U(s)=t。domUp:U(p)。定义program-size 复杂性（Kolmogorov熵） HC(x) min|p|:p&C(p)=xC是某

3、台具体的机器，可构造通用机U使得： U(1#C0p)=C(p) 这里#C指C的哥德尔数。6定义算法概率： PC(x)C(p)=x2-|p|停机概率即为UpdomU2-|p|定理2.1：H(x)=-log2P(x)+(1)7定义Joint complexity： H(x,y)min|p|:U(p)=定理2.2 H(x,y)H(x)+H(y)+(1) H(x,H(x)H(x)+(1)称x,y是算法独立的当且仅当H(x,y)H(x)+H(y)。x的elegant program x是计算x的最小程序。 显然，U(x )=x，H(x)=|x|，H(U(x)=|x|8定义Relative informa

4、tion content： H(x|y)min|p|:U(p,y)=x定理2.3：H(x,y)=H(x)+H(y|x)+(1)maxH(x):|x|=n=n+H(n)+(1)n+log2nH(1n)=H(n)+(1)log2n定义Mutual information content： I(x:y)H(x)+H(y)-H(x,y)I(x:y)=H(x)-H(x|y)+(1)=H(y)-H(y|x)+(1)9三、三、算法随机性算法随机性定义3.1(weak Chaitin randomness)对任意 ，称是weakly Chaitin random，如果c n+(H(n)n-c)。定义3.2(M

5、artin-Lf randomness) C+0,1是一个ML test，如果C是一个r.e.集，且n+(sCn2-|s|2-n，其中，Cns:(n,s)C。 对任意 ，称是ML random如果对任意的ML test C，nCn。10定义3.3(universal probability) 函数:0,10,1是lower-computable semi-measure 如果s0,1(s)1且(,s)Q0,1：(s)为r.e. 一个lower-computable semi-measure 是一个universal probability如果对任意lower-computable semi-m

6、easure ，c+s0,1(s)c(s)。对任意通用机U，2-Hu(s)和PU(s)都是universal probability。前面H(s)是由program-size定义的，这里可以给出另一种抽象定义：H(s)-log2(s)。11定义3.4(-likeness) 对任意的r.e. , dominates 如果有递归的递增有理数序列an、bn使得limnan=，limnbn=且c+n (c(-an)-bn)。 一个r.e.实数是-like如果它dominates 所有的r.e.实数。定理3.5 对任意的r.e.实数,如果 domintes 那么H(n)H(n)+(1)。定义3.6(un

7、iversality)一个递归的递增收敛有理数数列an是universal如果对任意递归的递增收敛有理数数列bn存在c+使得对所有的n ，有 c(-an)-bn，且limnan=，limnbn=。12定理3.7 01是一个r.e.实数，下面条件等价： 是weakly Chaitin random。kNk(nNk)H(n)n+k。 是ML random。n(An)2-nn(An)。(Ai)N(iN)(Ai)。 是-like。对任意r.e.实数，H(n)H(n)+(1)。存在通用机U，=U。有一个universal probability 使得=s0,1(s)。任意收敛到的递归递增有理数数列uni

8、versal。有一个universal递归递增有理数数列收敛到。13四、四、智慧的智慧的与不完全性与不完全性定理4.1 给定n，可以判定U在所有那些长度不超过n的程序上是否会停机。 证明：显然，nn+2-n。 楔形计算：U第一次执行第一个输入的第一步操作，第二次执行第一个输入的第二步和第二个输入的第一步第i次执行第k个输入的第j步，i=j+k。一旦某个p停止，循环执行+2-|p|可逼近直到 n 。假若还有长度短于n的程序p停止则2-|p|2-n ，那么将有n+2-n+2-|p|，而这与nn+2-n矛盾。14定理4.2 是weakly Chaitin random。 证明：domU=p:U(p)

9、=p1,p2,p3 r.e. 定义nin 2-|pi| 显然nn+1 顺序计算k，k=1,2,3直到kn 即有nkn。即存在部分递归函数使得(n)=x，其中H(x)n。 所以有nH(n)H(n)+c 15定理4.3 有一指数丢番图方程A(n,x1,x2,xm)=0，如果的第n个元素是0，则方程只有有穷多解；如果的第n个元素是1，则方程有无穷多解。 证明：由4.2中的证明过程，=limnn 集合R=(n,k):k的第n个元素是1是r.e.集。 由Matiyasevich：每一个递归可枚举集有一个singlefold指数丢番图方程表示。即：pR iff !y(A(p,y)=0)。p和y都可以是多元

10、组。这里的p是，y是。 因此，丢番图方程A(n,k,x2,xm)=0有唯一解x2,xm如果k的第n个元素是1；否则，无解。所以，如果的第n个元素是1，则A(n,x1,x2,xm)=0有无穷多解x1,x2,xm；否则，有穷。16希尔伯特第十问题的否定解决告诉我们不存在普遍算法判定任意丢番图方程是否有整数解，此定理则显示情况更糟，对于指数丢番图方程A(n,x1,x2,xm)=0中一个参数n的改变，方程是否有无穷解的波动竟然是算法随机的！17定理4.4 FAS是一个每个在其中可证的算术命题都真的可递归公理化的形式系统，如果形如“H(s)n”的命题可证那么一定有nH(axioms)+(1)。 证明：按

11、证明长度枚举FAS的定理，对任意的正整数k，定义s为形如“H(s)n”的且满足nH(axioms)+k的枚举序列中的第一个定理。由s的定义方式借助Church-Turing论题，存在部分递归函数?使得s=?(axioms,H(axioms),k) 由定理2.2 H(s)H(axioms,H(axioms),k)+c?H(axioms)+H(k)+(1) H(axioms)+kH(s)H(axioms)+H(k)+(1) kH(axioms)+k0”18定理4.4以及前面的定理4.2和后面的图灵停机定理的证明思想可对比“不存在最无趣的自然数”和“n是不能被少于二十个字定义的最小自然数。”19定理

12、4.5 任何包括初等数论可递归公理化的协调FAS只能判定的有穷个元素。定理4.6 对于i0，考虑r.e.随机实数=0.a0a1a2ai-1aiai+1其中a0=a1=a2=ai-1=1，ai=0。可以能行的构造通用Chaitin机U（依赖于ZFC和）满足如下条件： 1.在PA内可证明U的通用性。 2.ZFC只能判定U的前i项。 3. =U 注：取i=0，则ZFC不能判定U的任何项。20综合定理4.3、4.5，任何形式理论只能对有穷多个n确定丢番图方程A(n,x1,x2,xm)=0是有有穷解还是无穷解。由定理4.1，假如给定了10000，那么长度短于10000的程序的停机问题将得到解决，事实上，

13、这些程序将包括为费马大定理、哥德巴赫猜想、黎曼假设等重要命题寻找反例的程序！对任意的FAS，如果H(FAS)n-(1)，它与随机串是递归不可区分的，它也是浅的。23结合前一节，我们知道，是不可计算的，虽然逼近的前几步操作是容易的，因为前面的短程序要么是语法错误的要么很快停机要么很容易看出它永不停机，但想要计算出10000显然也并不现实。另一方面，即使知道了n，判定那些长度短于n的程序耗费的时间t(n)的增长速度将快于任何递归函数。这可看作另一种形式的BusyBeaver函数。因此，无比诱人，却毫无用处！24六、六、 Digital philosophy与不完全与不完全程序 计算机 输出公理 F

14、AS 定理科学理论 推演 经验材料DNA 演化 有机体终极真理 上帝 宇宙25有无穷多的真命题具有太高的复杂性，它们不可能被“压缩”进一个FAS，类如判定的二进制展开式的某一位是0还是1这种形式的命题，不但超出了任何FAS的界限，而且因其随机性，要得到它们的最好方式恐怕是：直接把它们作为公理添加到系统中去！“不劳无获！”更多输出？更多输入！证明越多，假设越多！PNP26it from bit!WheelerAll is computation!Wolfram对于有限序列，非随机数集是simple set。而实数轴上非随机数的测度为0。“上帝不仅在量子力学里掷骰子，而且在算术里掷骰子”Chait

15、in所以，有理由大胆猜测：整个宇宙都是随机的。但从这种观点看，“终极真理”绝不会简洁（如果存在的话），它甚至跟整个宇宙一样臃肿。27如果宇宙是随机的，为什么现代科学的发展一再向我们保证，自然是可以认识的，人类的存在绝不是一场悲剧？因为可以严格证明，即使对于有限随机序列，在某种程度的高复杂性下必然会出现某些长度的有规律的块（如连续n个1的块），最随机的序列必然包含对数阶长度的非常规则的子序列。也许我们所处的世界可能是极大随机的宇宙中一片规则的绿洲。“面对着大自然朝着无序发展的势不可挡的趋向，我们宣告自己的本性，建立起一个有组织的飞地，这是对众神及他们所强加给我们的铁一般的必然性的鄙视，这是不幸之

16、所在，也是荣耀之所在”维纳。28“他（罗素）把逻辑和数学公理同自然律相比，把逻辑证据和感官知觉相比，以致公理无需必然是自明的，它们的合理性毋宁依赖于这样一个事实（恰和物理学一样）：它们使得这些感官知觉的推演成为可能对于抽象集合论的某些问题的判定，甚至对于某些有关的实数论问题，建立在某一迄今未知的思想之上的新公理将是必要的。或许，某些其他数学问题多年来所呈现的看来不可克服的困难，也是由于必要的公理还没有找到这一事实。当然，在这些情况下，数学可能会丧失许多绝对确定性；但在数学基础的现代批评的影响下，这在很大程度上已经发生了。”哥德尔29“即使不考虑某一新公理的内在必然性，甚至在它根本就没有什么内在

17、必然性的情况下，关于它的真理性的概然判定从另一条道路来说也是可能的，即归纳的研究它的成功。这里成功的意思是在推论上的多成果性可能存在这样一些公理以致不管它们是否内在必然，这些公理至少应在和任何公认的物理理论一样的意义上被接受。”哥德尔If mathematics describes an objective world just like physics, there is no reason why inductive methods should not be applied in mathematics just the same as in physics.Gdel30附录附录哥德尔不

18、完全性定理哥德尔不完全性定理31图灵停机定理：停机问题不可解，即对于任何声称要判定所有图灵机程序是否停机的图灵机程序H，都存在一个程序P和输入数据I，使程序H不能判定处理数据I时，P是否会停机。 证明：假设存在停机程序H，构造如下程序V： 1 输入N。 2 生成大小不超过N的所有程序P1,P2,P3Pn。 3 检查2中所有程序是否停机，排除所有不停机的。 4 模拟3得到的所有停机程序的运行。 5 取4中最大的输出，乘以2作为V的输出。 上面构造的程序V显然对于任意的N都停机，它的长度为logN+(1)。取足够大的N，有logN+(1)N，所以V就是某个Pi，它的输出是自己输出的两倍，矛盾！ 由此易见K=a:?a(a)是r.e.集但不是递归集。32哥德尔不完全性定理：Th不能递归公理化。 证明：因为K递归可枚举，在中可定义，所以有公式(x)在中定义K。 aKc iff (Sa0)Th 任给a，可能行的找到(Sa0)，所以借助Church-Turing论题，存在f使得 aKc iff f(a)=#(Sa0)#Th Kcm# Th 假设Th可递归公理化，则# Th递归可枚举，所以Kc也递归可枚举，所以K就是递归的。矛盾！33参考文献参考文献A.Nies.Computability and Rand