期刊文献+

Grzegorczyk分层的一种延伸

AN EXTENSION OF Grzegorczyk's HIERARCHY
下载PDF
导出
摘要 本文讨论某些递归函数类的分层问题.首先给出的是原始的Gorzegorczyk分层的一种较为简单的等价定义.然后,作为对Ackermann函数的一种推广,定义了一个递归函数序列{An}n∈ω.并以此作为分层函数列定义了一种新的递归分层{Zn}n∈ω(即Z—分层),这种分层涉及了比原始递归函数类更大的一个违归函数类.实际上,原始递归函数类仅是Z—分层的第一层Z0.而且这种分层的任意的第n+1层都含有前面一层的通用函数.最后还定义了Z—分层的一种加细{Z}n,i∈ω,使得{Z}i∈ω构成Zn的一种合理分层,并且在Z0上的加细{Z}i∈ω刚好就是原始的Grzegorczyk分层.这表明Z—分层及其加细确为Grzegorczyk分层的自然延伸. This paper discusses the hierarchies of some classes of recursive functions. A simple equivalent definition of original Grzegorczyk's hierarchy is presented at first. Then the authors define by the generalization of Ackermann's function a sequence of recursive functions {An}n∈ω, based on which they define hierarchy, {Zn}n∈ω(the Z-hierarchy)of a class of recursive functions which is much larger than the class of primitive recursive functions.The first level Z0 of this hierarchy is just the class of primitive recursive functions.For all n, Zn+1 contains the universal function of its predecessor Zn. A refinement {Z}n, i∈ωof Z-hierarchy is defined at last by the natural hierarchy of each Zn. The refinement on Z0 is same as the original Grzegorczyk's hierarchy. This shows that their Z-hierarchy and its refinement are really a natural extension of Grzegorczyk's hierarchy.
作者 郑锡忠 钱磊
机构地区 南京大学
出处 《软件学报》 EI CSCD 北大核心 1994年第3期55-64,共10页 Journal of Software
基金 国家自然科学基金
关键词 递归函数 G-分层 分层 Z-分层 Hierarchy Grzegorczyk's hierarchy Z-hierarchy.
  • 相关文献

参考文献3

  • 1郑锡忠,1991年
  • 2莫绍揆,递归论,1987年
  • 3张鸣华,可计算性理论,1984年

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部