加速定理与函数分层

加速定理与函数分层

ID:14543505

大小:41.00 KB

页数:10页

时间:2018-07-29

加速定理与函数分层_第1页
加速定理与函数分层_第2页
加速定理与函数分层_第3页
加速定理与函数分层_第4页
加速定理与函数分层_第5页
资源描述:

《加速定理与函数分层》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、加速定理与函数分层人做了书的奴隶,便把活人带死了。……把书作为人的工具,则书本上的知识便活了。有了生命力了。——华罗庚加速定理与函数分层王永革(南开数学研究所)Speed-upTheoremandHierarchyoftheRecursiveFunctionsWangYongge(NankaiInstituteofMathematicsNankaiUniversity)AbstractInthispaper,we'llintroduceakindofO(F)-LOOPoperator,whichwillleadtoahierarchyofanyrecu

2、rsivefunctions:O(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,wec

3、angraspthesoulofSpeed-uptheoreminamorehigherlevel.摘要本文引进一种O(F)-LOOP算子,通过该算子可对一般递归函数集进行分层,且该算子对应于计算复杂性中的加速定理。由此我们得到加速定理的定量描述。§1引言Grzegorczyk在文[6]中对原始递归函数进行分层,这种分层等价于通过递归算子的使用次数而对原始递归函数进行的分层,但这种分层仅仅是对应于原始递归函数的。那么原始递归函数以外呢?本文将引进一种O(F)-LOOP算子,由它出发可对任意的递归函数集进行分层,同时我们证明了Grzegorczyk的分层

4、与本文的分层具有非常良好的性质:它们对应于加速定理。§2程序语言O(F)-LOOP  以下各节的研究基于一种程序语言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为一给定函数集,则

5、O(F)-LOOP程序P可计算函数g(x1,...,xn)是指对于任意输入X1=x1,X2=x2,...,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)。 

6、 定义2.2容许循环指令最多嵌套n层的所有O(F)-LOOP程序组成的集合记为O(F)-LOOPn。显然,∪O(F)-LOOP_n就是所有O(F)-LOOP程序的集合。§3E-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,A

7、F(0,1)=2,AF(0,n)=max{f1(n),f2(n,n),...,fm(n,...,n)}(n≥2)AF(m+1,n+1)=AF(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(

8、un+1(x))性质3.2un(k)(x)≥k性质3.3un(x)>x性质3.4un(x+1)

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。