资源描述：
《加速定理及函数分层60403》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、加速定理与函数分层60403读书时，我愿在每一个美好思想的面前停留，就像在每一条真理面前停留一样。——爱默生加速定理与函数分层王永革(南开数学研究所)Speed-upTheoremandHierarchyoftheRecursiveFunctionsWangYongge(NankaiInstituteofMathematicsNankaiUniversity)AbstractInthispaper,we'llintroduceakindofO(F)-LOOPoperator,whichwillleadtoahierarchyofanyrecursivefunctions:O
2、(F)=O(F)n.We'veprovedthatthishierarchycorrespondstothespeed-uptheorem,i.e.givenanyr(x)∈O(F)_i,thereisalanguagehavingO(F)i+1complexitywhichcanbespeededupbyr(x),andalsothereisar(x)inO(F)i,sothatanylanguagehavingO(F)icomplexitycannotbespeededupbyr(x).Throughthis,wecangraspthesoulofSpeed-upthe
3、oreminamorehigherlevel.摘要本文引进一种O(F)-LOOP算子，通过该算子可对一般递归函数集进行分层，且该算子对应于计算复杂性中的加速定理。由此我们得到加速定理的定量描述。§１引言Grzegorczyk在文[6]中对原始递归函数进行分层,这种分层等价于通过递归算子的使用次数而对原始递归函数进行的分层，但这种分层仅仅是对应于原始递归函数的。那么原始递归函数以外呢？本文将引进一种O(F)-LOOP算子，由它出发可对任意的递归函数集进行分层，同时我们证明了Grzegorczyk的分层与本文的分层具有非常良好的性质:它们对应于加速定理。§２程序语言O(F)-L
4、OOP 以下各节的研究基于一种程序语言O(F)-LOOP，为此我们先来介绍这种语言。本语言中,用一些字符表示变量.特别地，将 X1,X2,...和Y分别称为输入变量和输出变量，将Z1,Z2,...称为局部变量。O(F)-LOOP的指令共有以下六种：1.V←0(零指令)2.V←V+1(加1指令)3.V←V'(赋值指令)4.LOOPV(循环指令)5.END(循环返回指令)6.V←O(f(v1,...,Vn))(f∈F,本指令称为Oracle指令)定义2.1设F为一给定函数集，则O(F)-LOOP程序P可计算函数g(x1,...,xn)是指对于任意输入X1=x1,X2=x2,
5、...,Xn=xn程序P的输出Y为g(x1,...,xn)例如：对于下述程序PZ1←X1+1Z2←Z2+1LOOPZ2Z2←Z2+1ENDZ3←O(f(Z2))(f∈F)Y←Z3设输入x1=1,x2=2。程序执行到第三条指令LOOPZ2时，Z2=3，故由第三到第五条指令组成的循环体重复执行三次。注意：循环体内第四条指令使Z2值发生变化，但这不再影响本循环重复执行的次数。程序执行完毕后输出y=f(6)。事实上，本程序所能计算的函数为y=f(2x_1+4)。 定义2.2容许循环指令最多嵌套n层的所有O(F)-LOOP程序组成的集合记为O(F)-LOOPn。显然，∪O(F)-L
6、OOP_n就是所有O(F)-LOOP程序的集合。§３E-Ackermann函数为了方便起见，以下各节都假定：F={f1,...,fm}是满足下述条件的有穷函数集：(1).对于1≤i≤m，fi(x)是全定义的；(2).f1(x)=x+2,f2(x,y)=max{x,y}；(3).3≤i≤m时，fi(x1,...,xn)对于每一分量都是单调不减的。定义3.1定义以F为基始的E-Ackermann函数AF(m,n)为：AF(0,0)=1,AF(0,1)=2,AF(0,n)=max{f1(n),f2(n,n),...,fm(n,...,n)}(n≥2)AF(m+1,n+1)=AF(
7、m,AF(m+1,n))并称如下定义的函数序列{u_n(x)}为A_F(m,n)导出的层次函数：un(x)=AF(n,x)易知u0(0)=1,u_0(1)=2,u0(x)=max{x+2,x,f3(x,...,x),...,fm(x,...,x)}(x≥2)un+1(x)=un(x)(1)这里u_n^{(x)}=u_n...u_n(1)下边我们给出{un(x)}的一些基本性质：性质3.1un+1(x+1)=un(un+1(x))性质3.2un(k)(x)≥k性质3.3un(x)>x性质3.4un(x+1)>un(x
